You have a one-indexed array of length . This array is special: each value will occur at most times in the array.
You also decided on a value , where . You can then perform the following operation any number (possibly zero) of times:
- Choose an index (, and swap with .
Please output the lexicographically smallest array that can be made if you choose the optimal value of . An array is lexicographically smaller than an array if there is some index such that and for all .
Input Specification
The first line will contain the integer .
The next line will contain integers, . It is guaranteed that each value of will occur at most times.
Output Specification
Output the lexicographically smallest array that can be made if the optimal value of is chosen.
Subtasks
Subtask 1 [12%]
Subtask 2 [27%]
Subtask 3 [61%]
Sample Input for Subtask 1
5
5 4 3 2 1
Sample Output for Subtask 1
1 2 3 4 5
Sample Input for Subtask 2
6
3 1 1 1 1 2
Sample Output for Subtask 2
1 1 1 1 3 2
Explanation for Sample for Subtask 2
One optimal value of is .
Sample Input for Subtask 3
11
5 1 2 1 2 1 2 1 1 2 100
Sample Output for Subtask 3
1 1 1 1 2 5 2 2 1 2 100
Comments