“There must be an end to every beginning”
For a sequence $A = (a_1, a_2, \dots, a_m)$, define:
- the length of the strict longest increasing subsequence: $$\text{LIS}(A) = \max\{k \mid \exists 1 \le i_1 < i_2 < \dots < i_k \le m, a_{i_1} < a_{i_2} < \dots < a_{i_k}\}$$
- the length of the strict longest decreasing subsequence: $$\text{LDS}(A) = \max\{k \mid \exists 1 \le i_1 < i_2 < \dots < i_k \le m, a_{i_1} > a_{i_2} > \dots > a_{i_k}\}$$
For any sequence $A$, define $f(A)$ as the maximum integer $k$ satisfying the following conditions:
There exist $k$ real numbers $x_1, x_2, \dots, x_k$. After appending them to the end of $A$ in order, we obtain a new sequence $B = (a_1, a_2, \dots, a_m, x_1, x_2, \dots, x_k)$, and the following conditions hold:
- All elements in sequence $B$ are pairwise distinct;
- $\text{LIS}(B) = \text{LIS}(A)$;
- $\text{LDS}(B) = \text{LDS}(A)$.
Now given a permutation $P = (P_1, P_2, \dots, P_n)$ of length $n$, for each prefix $P^{(i)} = (P_1, P_2, \dots, P_i)$, you need to compute $f(P^{(i)})$ and output all answers.
“One day I will return to your side”
Input
The first line contains an integer $T$ ($1 \le T \le 10^5$), denoting the number of test cases.
For each test case:
- The first line contains an integer $n$ ($1 \le n \le 2 \cdot 10^5$);
- The second line contains $n$ integers $P_1, P_2, \dots, P_n$ ($1 \le P_i \le n$), representing a permutation of length $n$.
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 one line containing $n$ integers representing the answers.
Examples
Input 1
5 2 1 2 3 1 3 2 4 3 4 1 2 5 2 5 1 3 4 6 3 6 2 1 4 5
Output 1
0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1 2 1 2