“凡事皆有终结”

对于序列 $A = (a_1, a_2, \dots, a_m)$，定义：

• 严格最长上升子序列的长度： $$\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}\}$$
• 严格最长下降子序列的长度： $$\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}\}$$

对于任意序列 $A$，定义 $f(A)$ 为满足以下条件的最大整数 $k$：

存在 $k$ 个实数 $x_1, x_2, \dots, x_k$。按顺序将它们追加到 $A$ 的末尾后，我们得到一个新序列 $B = (a_1, a_2, \dots, a_m, x_1, x_2, \dots, x_k)$，且满足以下条件：

1. 序列 $B$ 中的所有元素两两不同；
2. $\text{LIS}(B) = \text{LIS}(A)$；
3. $\text{LDS}(B) = \text{LDS}(A)$。

现在给定一个长度为 $n$ 的排列 $P = (P_1, P_2, \dots, P_n)$，对于每个前缀 $P^{(i)} = (P_1, P_2, \dots, P_i)$，你需要计算 $f(P^{(i)})$ 并输出所有答案。

“终有一天，我会回到你的身边”

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 10^5$)，表示测试用例的数量。

对于每个测试用例：

• 第一行包含一个整数 $n$ ($1 \le n \le 2 \cdot 10^5$)；
• 第二行包含 $n$ 个整数 $P_1, P_2, \dots, P_n$ ($1 \le P_i \le n$)，表示一个长度为 $n$ 的排列。

保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

输出格式

对于每个测试用例，输出一行，包含 $n$ 个整数，表示答案。

样例

输入样例 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

输出样例 1

0 0
0 0 0
0 0 1 0
0 0 1 0 0
0 0 1 2 1 2