CF1951H Thanos Snap

[Piotr Rubik - Psalm dla Ciebie](https://youtu.be/3WWwuA6twKI) ඞ There is an array $ a $ of size $ 2^k $ for some positive integer $ k $ , which is initially a permutation of values from $ 1 $ to $ 2^k $ . Alice and Bob play the following game on the array $ a $ . First, a value $ t $ between $ 1 $ and $ k $ is shown to both Alice and Bob. Then, for exactly $ t $ turns, the following happens: - Alice either does nothing, or chooses two distinct elements of the array $ a $ and swaps them. - Bob chooses either the left half or the right half of the array $ a $ and erases it. The score of the game is defined as the maximum value in $ a $ after all $ t $ turns have been played. Alice wants to maximize this score, while Bob wants to minimize it. You need to output $ k $ numbers: the score of the game if both Alice and Bob play optimally for $ t $ from $ 1 $ to $ k $ .

Each test contains multiple test cases. The first line contains an integer $ t $ ( $ 1 \le t \le 10^4 $ ) — the number of test cases. The description of the test cases follows. The first line of each test case contains an integer $ k $ ( $ 1 \le k \le 20 $ ) — the parameter of the size of $ a $ . The second line of each test case contains $ 2^k $ integers $ a_1, a_2, \ldots, a_{2^k} $ ( $ 1 \le a_i \le 2^k $ , $ a_i $ 's are pairwise distinct) — the given array $ a $ . It is guaranteed that the sum of $ 2^k $ over all test cases does not exceed $ 2^{20} $ .

For each test case, print $ k $ numbers, where the $ i $ -th number is the score of the game if both Alice and Bob play optimally for $ t = i $ .

In the third test case, for $ t = 2 $ , the game could have proceeded as follows: - Initially, $ a = [5, 1, 6, 4, 7, 2, 8, 3] $ . - Alice swaps $ a_6 $ and $ a_8 $ , $ a $ becomes $ [5, 1, 6, 4, 7, 3, 8, 2] $ . - Bob erases the right half of the array, $ a $ becomes $ [5, 1, 6, 4] $ . - Alice does nothing, $ a $ remains as $ [5, 1, 6, 4] $ . - Bob erases the right half of the array, $ a $ becomes $ [5, 1] $ . - The game ends with a score of $ 5 $ .