Морти и пароль

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

Рик выставил в ряд перед Морти $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$ целых чисел через пробел --- пароль от сейфа.

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