| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 9 | 6 | 6 | 85.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$ целых чисел через пробел --- пароль от сейфа.
5 5 4 3 2 1
5 4 3 2 1
7 7 1 2 3 4 5 6
7 3 4 1 2 6 5
Перестановка $a$ длины $n$ лексикографически больше перестановки $b$ длины $n$, если существует такое $x$, что $a_i = b_i$ для всех $i$ от $1$ до $x - 1$ и $a_x > b_x$.