Universal Cup Judging System

Universal Cup

Limite de temps : 2.0 s Limite de mémoire : 1024 MB Points totaux : 100 Hackable ✓
Statistiques

“모든 시작에는 끝이 있기 마련이다”

수열 $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)$가 다음 조건을 만족합니다:

  1. 수열 $B$의 모든 원소는 서로 다릅니다;
  2. $\text{LIS}(B) = \text{LIS}(A)$;
  3. $\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

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.