Fișierul intrare/ieșire	sirmunte.in, sirmunte.out	Sursă	ad-hoc
Autor	din folclor	Adăugată de	Victor Manz • vmanz
Timp de execuție pe test	0.05 sec	Limită de memorie	2048 KB
Scorul tău	N/A	Dificultate	0.5

Vezi soluțiile trimise | Statistici

Șir munte

Un șir munte este un șir x = (x₀, x₁,..., x_n-1) cu proprietatea că există un indice k cu proprietățile:

• 0 < k < n-1
• x_i-1 < x_i pentru orice i, 1 ≤ i ≤ k
• x_i-1 > x_i pentru orice i, k < i < n

Scrieți un program care citește un șir munte x și afișează șirul obținut prin ordonarea crescătoare a termenilor lui x.

Date de intrare

Fișierul de intrare sirmunte.in conține pe prima linie n, reprezentând numărul termenilor șirului x, iar pe a doua linie, separați prin câte un spațiu, termenii șirului.

Date de ieșire

În fișierul de ieșire sirmunte.out vor fi afișați termenii șirului x în ordine crescătoare.

Restricții

• 3 ≤ n ≤ 100 000
• 0 ≤ x_i ≤ 1 000 000 000 pentru orice i, 0 ≤ i < n

Exemplu

sirmunte.in	sirmunte.out
6 1 5 8 6 1 0	0 1 1 5 6 8

Explicație

Șirul dat x = (1, 5, 8, 6, 1, 0) este un șir munte: 1 < 5 < 8 > 6 > 1 > 0.
Șirul obținut în urma ordonării crescătoare a termenilor lui x este (0, 1, 1, 5, 6, 8)