АЛГОРИТМЫН ЦАГААН ТОЛГОЙ

Сережа тоон дараалалд маш их дуртай. Ялангуяа шаталсан дараалалд.

 i (1 <= i <= |a|) индекстэй  a₁, a₂, ..., a_|a| дарааллын хувьд дараах нөхцлийг хангасан байх ёстой.

a1 < a2 < . . .  < ai − 1 < ai > ai + 1 > . . .  > a∣a∣ − 1 > a∣a∣.

Жишээлбэл: [1, 2, 3, 2] болон [4, 2] шаталсан дараалал. Харин [3, 1, 2] дарааллын хувьд биш.

Сережад m элементтэй тоон дараалал өгөгдсөн. Энэ дарааллаас хамгийн урт шаталсан дараалллыг гаргаж авахыг хүсчээ. Сережад тусла.

Input

Эхний мөрөнд m (1<=  m<=  10^5) тоо - Сережад байгаа элементийн тоо. Дараагийн мөрөнд m элементтэй b_i (1<=  b_i<=  5000) дараалал зайгаар тусгаарлагдан өгөгдөнө.

Output

Эхний мөрөнд шаталсан дарааллын урт. Дараагийн мөрөнд шаталсан дарааллыг зайгаар тусгаарлаж хэвлэ.

Example

Input 1:

5
1 2 3 4 5

Output 1:

5 4 3 2 1

Input 2:

6
1 1 2 2 3 3

Output 2:

1 2 3 2 1