Problem Description

Recently, someone gave the Cossack an array $a$ containing $n$ integers.

The bearded man immediately wants to sort the elements of the array so that after sorting, any two adjacent numbers in the array are different. Among all such sortings, he wants to find the lexicographically smallest one.

Recall that lexicographical order is defined as follows. Suppose there are two arrays. Find the first position where the elements of the two arrays differ. If at that position the element of the first array is smaller than that of the second array, then the first array is lexicographically smaller than the second; otherwise, the first array is lexicographically larger. For example, the following inequalities hold: $[10, 3, 1] < [10, 4, 5]$, $[1, 1, 1] < [1, 2, 3]$, $[1, 2, 3] < [10, 10, 10]$.

Input Format

The first line contains an integer $n$ $(1 \leq n \leq 5 \cdot 10^5)$, the number of elements in the array.

The second line contains $n$ integers $a_1, a_2, ..., a_n$ $(1 \leq a_i \leq 5 \cdot 10^5)$, the elements of the array.

Output Format

If it is impossible to sort the Cossack’s array, output a single number $-1$.

Otherwise, output $n$ integers, the lexicographically smallest valid sorting of the Cossack’s array.

5
3 1 2 3 3

3 1 3 2 3

6
2 3 1 1 2 4

1 2 1 2 3 4

4
1 2 1 1

-1

Hint

Sample Explanation

In the first sample, there is a unique sorting.

In the second sample, there are other sortings as well, for example: $[1, 2, 3, 4, 1, 2]$ or $[1, 4, 1, 2, 3, 2]$. But all these sortings are lexicographically greater than $[1, 2, 1, 2, 3, 4]$.

In the third sample, there is no valid sorting (the array will always have two $1$’s in adjacent positions).

Scoring Rules

This problem uses per-testpoint scoring. Some additional constraints are:

• (5 points): $n \leq 10^3, a_i \leq 2$
• (10 points): $n \leq 10^3, a_i \leq 3$
• (25 points): $n \leq 10^3, a_i \leq 5 \cdot 10^5$
• (5 points): $n \leq 5 \cdot 10^5, a_i \leq 2$
• (10 points): $n \leq 5 \cdot 10^5, a_i \leq 3$
• (45 points): $n \leq 5 \cdot 10^5, a_i \leq 5 \cdot 10^5$

Translated by DeepSeek V3.

Translated by ChatGPT 5