В государстве ММММ выбран новый парламент. Во время регистрации каждый член парламента получил свой уникальный целый положительный идентификационный номер. Номера были даны в случайном порядке, в последовательности номеров возможны промежутки. Кресла в парламенте расположены в виде дерева. Когда члены парламента вошли в зал, они заняли кресла в следующем порядке. Первый вошедший занял кресло председателя. Каждый из следующих делегатов направлялся влево, если его номер был меньше, чем председателя, или вправо в противном случае. После этого парламентарий занимал свободное кресло и объявлял себя председателем крыла. Если кресло председателя крыла уже было занято, то алгоритм рассадки продолжался таким же образом: делегат направлялся влево или вправо в зависимости от идентификационного номера председателя крыла.
Рисунок ниже показывает пример рассадки членов парламента, если они вошли в зал в следующем порядке: 10, 5, 1, 7, 20, 25, 22, 21, 27.
Во время первой сессии парламента было решено не менять рассадку в будущем. Также был принят порядок выступления. Если номер сессии был нечётный, тогда члены парламента выступали в следующем порядке: левое крыло, правое крыло, затем председатель. Если крыло содержало более одного парламентария, то их порядок был аналогичен: левое подкрыло, правое подкрыло, председатель крыла. Если номер сессии был чётный, порядок выступлений был другой: правое крыло, левое крыло, затем председатель. Для приведённого примера порядок выступлений на нечётных сессиях будет 1, 7, 5, 21, 22, 27, 25, 20, 10, а на чётных сессиях — 27, 21, 22, 25, 20, 7, 1, 5, 10.
Определите порядок выступлений для чётной сессии, если известен порядок выступлений для нечётной сессии.
Исходные данные
Первая строка ввода содержит N — общее количество парламентариев. Следующие строки содержат N целых чисел — идентификационные номера членов парламента в порядке их выступления во время нечётной сессии.
Общее количество членов парламента не превосходит 3000. Идентификационные номера не превосходят 65 535.
Результат
Вывод должен содержать идентификационные номера членов парламента в соответствии с порядком выступления на чётной сессии.
Пример
исходные данные | результат |
---|
9
1
7
5
21
22
27
25
20
10
| 27
21
22
25
20
7
1
5
10
|
Источник задачи: Четвертьфинал, центральный регион России, Рыбинск, 17–18 октября 2001