H. Median Deletion
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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

Input

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

Output

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

Example
Input
6
1
1
4
4 2 1 3
5
4 1 3 5 2
6
1 4 3 5 2 6
6
1 5 3 4 2 6
8
4 3 7 5 1 6 8 2
Output
1 
2 4 2 3 
3 2 5 2 3 
2 3 3 3 3 2 
2 3 5 5 3 2 
3 3 3 5 2 5 2 3
Note

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]$$$.