#P17951. Rounddog

Rounddog

Rounddog

对于序列 A=(a1,…,am)A=(a_1,\ldots,a_m),记 LIS⁡(A)\operatorname{LIS}(A) 为严格最长上升子序列长度,记 LDS⁡(A)\operatorname{LDS}(A) 为严格最长下降子序列长度。

定义 f(A)f(A) 为满足以下条件的最大整数 kk:存在 kk 个实数 x1,…,xkx_1,\ldots,x_k,将它们按顺序追加到 AA 末尾,得到

B=(a1,…,am,x1,…,xk),B=(a_1,\ldots,a_m,x_1,\ldots,x_k),

并满足:

  1. BB 的所有元素两两不同;
  2. LIS⁡(B)=LIS⁡(A)\operatorname{LIS}(B)=\operatorname{LIS}(A);
  3. LDS⁡(B)=LDS⁡(A)\operatorname{LDS}(B)=\operatorname{LDS}(A)。

给定长度为 nn 的排列 P=(P1,…,Pn)P=(P_1,\ldots,P_n)。对于每个前缀 P(i)=(P1,…,Pi)P^{(i)}=(P_1,\ldots,P_i),求 f(P(i))f(P^{(i)})。

注意:追加的数可以是任意实数,不限于整数或原排列的取值范围;只能追加到末尾,不能插入原序列中间。

输入格式

第一行一个整数 TT(1≤T≤1051\le T\le10^5)。

每个测试用例第一行一个整数 nn(1≤n≤2⋅1051\le n\le2\cdot10^5)。 第二行 nn 个整数 P1,…,PnP_1,\ldots,P_n,保证是 11 到 nn 的一个排列。

所有测试用例的 ∑n≤2⋅105\sum n\le2\cdot10^5。

输出格式

每个测试用例输出一行 nn 个整数,依次表示各前缀的答案。

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

输出

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