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