Морти и пароль
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

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

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

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

Входные данные

В первой строке задано целое число n (1 ≤ n ≤ 100 000) — количество стаканчиков.

Во второй строке задано n целых чисел a1, a2, ..., an (1 ≤ ai ≤ n) — числа на стаканчиках вначале эксперимента. Гарантируется, что все ai различны.

Выходные данные

Выведите 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, что ai = bi для всех i от 1 до x - 1 и ax > bx.