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).