Задача №113519. Swap
Вам предоставляется последовательность из n чисел x 1 , x 2 , ..., x n . Каждое число 1, 2, ..., n появляется ровно один раз в последовательности.
Вы можете изменить последовательность с помощью свопов. Существует n - 1 последовательных "поворотов" пронумерованных k = 2, 3, ..., n . При "повороте" k вы можете либо менять значения x k и x ⌊ k / 2⌋ в последовательности, либо ничего не делать.
Последовательность a 1 , a 2 , ..., a n лексикографически меньше, чем последовательность b 1 , b 2 , ..., b n , если существует индекс j (1 ≤ j ≤ n ) такой, что a k = b k для всех k < j и a j < b j .
Какова минимальная лексикографическая последовательность, которую вы можете получить?
Первая строка ввода содержит целое число n.
Вторая строка ввода содержит n целых чисел: числа в последовательности.
Вы должны вывести n целых чисел: лексикографически минимальную последовательность.
Подгруппа 1(10 баллов)
1 ≤ n ≤ 20
Подгруппа 2(11 баллов)
1 ≤ n ≤ 40
Подгруппа 3(27 баллов)
1 ≤ n ≤ 1000
Подгруппа 4(20 баллов)
1 ≤ n ≤ 5 * 10 4
Подгруппа 5(32 балла)
1 ≤ n ≤ 2 * 10 5
5 3 4 2 5 1
2 1 3 4 5