Sắp xếp 3

Tác giả:

Dạng bài

Ngôn ngữ cho phép

Assembly, Awk, C, C#, C++, Clang, Cobol, D, ~~Groovy~~, Haskell, JS, Java, Kotlin, Lua, Node JS, OCaml, ObjectiveC, Output, PHP, Pascal, Perl, Prolog, Pypy, Pypy 3, Python, Ruby, Rust, Scala, Scratch, ~~Swift~~

Điểm: 1100 Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Trong một vương quốc nọ, nhà vua sở hữu một bộ sưu tập các viên ngọc quý, mỗi viên ngọc được khắc một mã số nguyên. Để chuẩn bị cho lễ hội hoàng gia, nhà vua muốn người quản kho sắp xếp lại các viên ngọc này theo một quy tắc đặc biệt:

Những viên ngọc có tần suất xuất hiện nhiều hơn (số lượng nhiều hơn) sẽ được ưu tiên xếp trước.
Nếu có nhiều loại ngọc có cùng tần suất xuất hiện, loại ngọc nào có mã số lớn hơn sẽ được ưu tiên xếp trước.

Bạn hãy giúp người quản kho thực hiện nhiệm vụ này.

Input

Dòng đầu tiên chứa một số nguyên dương \(n\) (\(1 \le n \le 10^5\)) là số lượng viên ngọc.
Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \dots, a_n\) (\(|a_i| \le 10^9\)) là mã số của các viên ngọc.

Output

In ra một dòng duy nhất chứa \(n\) số nguyên là mã số của các viên ngọc sau khi đã được sắp xếp theo yêu cầu của nhà vua.

Example

Test 1

Input

7
1 3 2 2 1 3 4

Output

3 3 2 2 1 1 4

Note

Các mã số \(1, 2, 3\) đều xuất hiện \(2\) lần.
Mã số \(4\) xuất hiện \(1\) lần.
Do tần suất của \(1, 2, 3\) bằng nhau và lớn hơn tần suất của \(4\), ta xét giá trị của chúng: \(3 > 2 > 1\).
Vậy thứ tự sắp xếp là: hai số \(3\), sau đó đến hai số \(2\), hai số \(1\) và cuối cùng là số \(4\).

Test 2

Input

5
5 5 1 2 2

Output

5 5 2 2 1

Scoring

Subtask \(1\) (\(40\%\) số điểm): \(n \le 10^3, |a_i| \le 10^3\).
Subtask \(2\) (\(60\%\) số điểm): Không có ràng buộc gì thêm.

Bình luận

Tải bình luận...

Không có bình luận nào.