Permus

Cerință

Se dă un șir $a$ de $n$ numere $a_1,a_2,\ldots,a_n$.

Aflați șirul minim lexicografic$^1$ $b_1,b_2,\ldots,b_n$ care să respecte următoarele condiții:

• Șirul $b$ se poate obține prin rearanjarea elementelor din $a$.
• $b_i \neq b_{i+1}$ pentru orice $i$, $1 \le i < n$.

În cazul în care nu există niciun șir $b$ care să respecte aceste proprietăți, afișați -1.

$^1$ Șirul $x_1,x_2,\ldots,x_n$ este mai mic lexicografic decât șirul $y_1,y_2,\ldots,y_n$ dacă există o poziție $p$ ($1 \le p \le n$) astfel încât:

• $x_i=y_i$, pentru orice $1 \le i<p$.
• $x_p<y_p$.

Date de intrare

Pe prima linie a fișierului de intrare permus.in se va afla $n$ - lungimea șirului $a$.

Pe a doua linie se vor afla $n$ numere $a_1,a_2,\ldots,a_n$ - elementele șirului $a$.

Date de ieșire

Dacă există un șir $b$ care să respecte condițiile din enunț, afișați elementele șirului $b$. În caz contrar, afișați -1.

Restricții și precizări

• $1 \le n \le 2 \cdot 10^5$
• $1 \le a_i \le n$

Exemplul 1

permus.in

7
3 2 1 1 3 3 2

permus.out

1 2 3 1 3 2 3

Explicație

$[1,2,3,1,3,2,3]$ este șirul minim lexicografic care respectă condițiile din enunț.

Exemplul 2

permus.in

4
1 2 1 1

permus.out

-1

Explicație

Se poate demonstra că nu există niciun șir $b$ care să respecte condițiile din enunț.