Имеется массив \(a\) длины \(2^k\), который изначально является перестановкой значений от \(1\) до \(2^k\) для некоторого целого положительного числа \(k\). Алиса и Боб играют в следующую игру на массиве \(a\). Сначала Алисе и Бобу даётся значение \(t\) между \(1\) и \(k\). Затем, ровно \(t\) ходов происходит следующее:
- Алиса либо ничего не делает, либо выбирает два различных элемента массива \(a\) и меняет их местами.
- Боб выбирает либо левую половину, либо правую половину массива \(a\), и стирает её.
Счет игры определяется как максимальное значение в \(a\) после всех \(t\) ходов. Алиса хочет максимизировать этот счет, а Боб — минимизировать.
Вам нужно вывести \(k\) чисел: счет игры, если и Алиса, и Боб играют оптимально, для всех \(t\) от \(1\) до \(k\).
Выходные данные
Для каждого набора входных данных выведите \(k\) чисел, где \(i\)-е число — это счет игры, если Алиса и Боб играют оптимально, а игра длится \(t = i\) ходов.
Примечание
В третьем наборе входных данных, для \(t = 2\), игра могла бы проходить следующим образом:
- Изначально, \(a = [5, 1, 6, 4, 7, 2, 8, 3]\).
- Алиса меняет местами \(a_6\) и \(a_8\), \(a\) становится \([5, 1, 6, 4, 7, 3, 8, 2]\).
- Боб стирает правую половину массива, \(a\) становится \([5, 1, 6, 4]\).
- Алиса ничего не делает, \(a\) остается \([5, 1, 6, 4]\).
- Боб стирает правую половину массива, \(a\) становится \([5, 1]\).
- Игра заканчивается со счётом \(5\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
1
1 2
2
4 3 2 1
3
5 1 6 4 7 2 8 3
4
10 15 6 12 1 3 4 9 13 5 7 16 14 11 2 8
5
32 2 5 23 19 17 31 7 29 3 4 16 13 9 30 24 14 1 8 20 6 15 26 18 10 27 22 12 25 21 28 11
|
1
3 1
7 5 1
15 13 9 1
31 28 25 17 1
|