“모든 시작에는 끝이 있기 마련이다”
수열 $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