「始まりあるものには必ず終わりがある」
数列 $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)$ が以下の条件を満たす:
- 数列 $B$ のすべての要素は互いに異なる;
- $\text{LIS}(B) = \text{LIS}(A)$;
- $\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)})$ を計算し、すべての答えを出力してください。
「いつの日か、私はあなたのそばへ戻るだろう」
入力形式
1 行目には、テストケースの数を表す整数 $T$ ($1 \le T \le 10^5$) が与えられます。
各テストケースについて:
- 1 行目には、整数 $n$ ($1 \le n \le 2 \cdot 10^5$) が与えられます;
- 2 行目には、長さ $n$ の順列を表す $n$ 個の整数 $P_1, P_2, \dots, P_n$ ($1 \le P_i \le n$) が与えられます。
すべてのテストケースにおける $n$ の総和は $2 \cdot 10^5$ を超えないことが保証されます。
出力形式
各テストケースについて、答えを表す $n$ 個の整数を 1 行に出力してください。
入出力例
入力例 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