Permus

Time limit: 0.25s Memory limit: 256MB Input: permus.in Output: permus.out

Cerință

Se dă un șir aa de nn numere a1,a2,,ana_1,a_2,\ldots,a_n.

Aflați șirul minim lexicografic1^1 b1,b2,,bnb_1,b_2,\ldots,b_n care să respecte următoarele condiții:

  • Șirul bb se poate obține prin rearanjarea elementelor din aa.
  • bibi+1b_i \neq b_{i+1} pentru orice ii, 1i<n1 \le i < n.

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

1^1 Șirul x1,x2,,xnx_1,x_2,\ldots,x_n este mai mic lexicografic decât șirul y1,y2,,yny_1,y_2,\ldots,y_n dacă există o poziție pp (1pn1 \le p \le n) astfel încât:

  • xi=yix_i=y_i, pentru orice 1i<p1 \le i<p.
  • xp<ypx_p<y_p.

Date de intrare

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

Pe a doua linie se vor afla nn numere a1,a2,,ana_1,a_2,\ldots,a_n - elementele șirului aa.

Date de ieșire

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

Restricții și precizări

  • 1n21051 \le n \le 2 \cdot 10^5
  • 1ain1 \le a_i \le n
# Punctaj Restricții
1 10 Există maxim două elemente elemente distincte în șirul aa
2 15 Toate elementele din șirul aa au frecvența mai mică sau egală cu 22
4 45 n2000n \le 2000
5 30 Fără restricții suplimentare

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][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 bb care să respecte condițiile din enunț.

Log in or sign up to be able to send submissions!