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

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

Median Deletion

Examples