Rounddog
对于序列 A=(a1,…,am),记 LIS(A) 为严格最长上升子序列长度,记 LDS(A) 为严格最长下降子序列长度。
定义 f(A) 为满足以下条件的最大整数 k:存在 k 个实数 x1,…,xk,将它们按顺序追加到 A 末尾,得到
B=(a1,…,am,x1,…,xk),
并满足:
- B 的所有元素两两不同;
- LIS(B)=LIS(A);
- LDS(B)=LDS(A)。
给定长度为 n 的排列 P=(P1,…,Pn)。对于每个前缀 P(i)=(P1,…,Pi),求 f(P(i))。
注意:追加的数可以是任意实数,不限于整数或原排列的取值范围;只能追加到末尾,不能插入原序列中间。
输入格式
第一行一个整数 T(1≤T≤105)。
每个测试用例第一行一个整数 n(1≤n≤2⋅105)。
第二行 n 个整数 P1,…,Pn,保证是 1 到 n 的一个排列。
所有测试用例的 ∑n≤2⋅105。
输出格式
每个测试用例输出一行 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
输出
0 0
0 0 0
0 0 1 0
0 0 1 0 0
0 0 1 2 1 2