CF2211H Median Deletion

You are given a permutation $ p $ of size $ n $ . You may perform the following operation any number of times: - Choose a subarray of size $ 3 $ . Then, delete the second smallest element within it. For example, for the permutation $ [2,4,5,3,1] $ , you may choose the subarray $ [\mathbf{2},\mathbf{4},\mathbf{5},3,1] $ . Since $ 4 $ is the second smallest element out of $ [2,4,5] $ , you can delete $ 4 $ to obtain the array $ [2,5,3,1] $ . For each $ i $ from $ 1 $ to $ n $ , find the minimum length of an obtainable array that contains the number $ p_i $ . Note that this problem is to be solved independently for each $ i $ .

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 10^4 $ ). The description of the test cases follows. The first line of each test case contains a single integer $ n $ ( $ 1 \le n \le 2 \cdot 10^5 $ ) — the length of the permutation. The second line of each test case contains $ n $ integers $ p_1, p_2, \ldots, p_n $ ( $ 1 \le p_i \le n $ ). It is guaranteed that the given $ p $ is a permutation. It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 2 \cdot 10^5 $ .

For each test case, output $ n $ numbers on a new line: the answer for $ i=1,2,\ldots,n $ .

In the second example, for $ i=1 $ , we can get an array of size $ 2 $ as follows: - Choose the subarray $ [4,2,1] $ . Delete the median $ 2 $ . The array is now $ [4,1,3] $ . - Choose the subarray $ [4,1,3] $ . Delete the median $ 3 $ . The array is now $ [4,1] $ . It can be shown that $ 2 $ is the minimum length of any reachable array that contains $ a_1=4 $ . For $ i=4 $ , the answer is $ 3 $ , with the minimum length reachable array containing $ a_4=3 $ being $ [4,1,3] $ .