Cossack Vus and Lexicography

Kozak recently received an array $a$ consisting of $n$ integers.

Vus wants to rearrange the elements of this array so that no two adjacent numbers are the same. Among all possible arrangements, he is interested in finding the lexicographically smallest one.

To clarify, lexicographical order is determined as follows: Given two arrays, identify the first position where they differ. If the element in the first array is smaller at this position, then the first array is considered lexicographically smaller. Conversely, if the element in the second array is smaller, then the first array is larger. For example, the following inequalities hold: $[10,3,1]$ < $[10,4,5]$, $[1,1,1]<[1,2,3]$, and $[1,2,3]<[10,10,10]$.

Input

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

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

Output

If it is impossible to rearrange Vus's array to meet the conditions, output a single number $-1$.

Otherwise, output $n$ integers representing the lexicographically smallest arrangement of Vus's array.

Examples

Note

In the first example, there is only one possible arrangement.

In the second example, other arrangements exist, such as $[1,2,3,4,1,2]$ or $[1,4,1,2,3,2]$. However, all these arrangements are lexicographically larger than $[1,2,1,2,3,4]$.

In the third example, no valid arrangement exists because the array will always have two adjacent ones.

Scoring

This problem uses post-test scoring with the following additional constraints:

• ($5$ points): $n\le 10^3,a_i\le 2$

• ($10$ points): $n\le 10^3,a_i\le 3$

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

• ($5$ points): $n\le 5\cdot 10^5,a_i\le 2$

• ($10$ points): $n\le 5\cdot 10^5,a_i\le 3$

• ($45$ points): $n\le 5\cdot 10^5,a_i\le 5\cdot 10^5$