“Mọi sự khởi đầu đều phải có kết thúc”
Với dãy $A = (a_1, a_2, \dots, a_m)$, định nghĩa:
- độ dài dãy con tăng nghiêm ngặt dài nhất: $$\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}\}$$
- độ dài dãy con giảm nghiêm ngặt dài nhất: $$\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}\}$$
Với mọi dãy $A$, định nghĩa $f(A)$ là số nguyên $k$ lớn nhất thỏa mãn các điều kiện sau:
Tồn tại $k$ số thực $x_1, x_2, \dots, x_k$. Sau khi nối chúng vào cuối dãy $A$ theo thứ tự, ta thu được dãy mới $B = (a_1, a_2, \dots, a_m, x_1, x_2, \dots, x_k)$ thỏa mãn các điều kiện sau:
- Tất cả các phần tử trong dãy $B$ đôi một khác nhau;
- $\text{LIS}(B) = \text{LIS}(A)$;
- $\text{LDS}(B) = \text{LDS}(A)$.
Bây giờ, cho một hoán vị $P = (P_1, P_2, \dots, P_n)$ có độ dài $n$, với mỗi tiền tố $P^{(i)} = (P_1, P_2, \dots, P_i)$, bạn cần tính $f(P^{(i)})$ và in ra tất cả các đáp án.
“Một ngày nào đó tôi sẽ trở về bên bạn”
Dữ liệu vào
Dòng đầu tiên chứa một số nguyên $T$ ($1 \le T \le 10^5$), biểu thị số lượng bộ dữ liệu.
Với mỗi bộ dữ liệu:
- Dòng đầu tiên chứa một số nguyên $n$ ($1 \le n \le 2 \cdot 10^5$);
- Dòng thứ hai chứa $n$ số nguyên $P_1, P_2, \dots, P_n$ ($1 \le P_i \le n$), biểu thị một hoán vị có độ dài $n$.
Dữ liệu đảm bảo tổng của $n$ trong tất cả các bộ dữ liệu không vượt quá $2 \cdot 10^5$.
Dữ liệu ra
Với mỗi bộ dữ liệu, in ra một dòng gồm $n$ số nguyên biểu thị đáp án.
Ví dụ
Dữ liệu vào 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
Dữ liệu ra 1
0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1 2 1 2