「凡事皆有終結」
對於序列 $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)})$ 並輸出所有答案。
「終有一日,我會返到你嘅身邊」
輸入格式
第一行包含一個整數 $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