시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 1024 MB96685.714%

문제

Однажды Рик решил проверить, насколько смекалист его внук Морти. Как известно, человек лучше думает в экстремальных ситуациях, поэтому Рик запер любимую Морти, Джессику, в комнате и повесил на дверь кодовый замок. Для того, чтобы ее спасти, Морти нужно провести эксперимент, который придумал Рик.

Рик выставил в ряд перед Морти $n$ стаканчиков с соком, на каждом из которых было написано целое число от $1$ до $n$. Число на $i$-м слева стаканчике было равно $a_i$. Кроме того, оказалось, что все числа на стаканчиках различны, то есть образовывали перестановку чисел от $1$ до $n$.

Рик разрешил Морти сколько угодно раз брать два соседних стаканчика и менять их местами. Морти очень боится, что никогда снова не увидит свою возлюбленную, поэтому у него трясутся руки, и, когда он меняет местами два стаканчика, из обоих стаканов выливается часть сока. Рик не хочет, чтобы Морти расплескал слишком много сока, поэтому он разрешил внуку прикасаться к каждому стаканчику не более двух раз. Паролем от сейфа является лексикографически максимальная перестановка чисел на стаканчиках, если смотреть слева направо, которая может получиться в результате эксперимента.

Помогите Морти найти пароль и спасти Джессику!

입력

В первой строке задано целое число $n$ ($1 \le n \le 100\,000$) --- количество стаканчиков.

Во второй строке задано $n$ целых чисел $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le n$) --- числа на стаканчиках вначале эксперимента. Гарантируется, что все $a_i$ различны.

출력

Выведите $n$ целых чисел через пробел --- пароль от сейфа.

예제 입력 1

5
5 4 3 2 1

예제 출력 1

5 4 3 2 1

예제 입력 2

7
7 1 2 3 4 5 6

예제 출력 2

7 3 4 1 2 6 5

노트

Перестановка $a$ длины $n$ лексикографически больше перестановки $b$ длины $n$, если существует такое $x$, что $a_i = b_i$ для всех $i$ от $1$ до $x - 1$ и $a_x > b_x$.