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