Universal Cup Judging System

Universal Cup

Límite de tiempo: 2.0 s Límite de memoria: 1024 MB Puntuación total: 100 Hackeable ✓
Estadísticas

「凡事皆有終結」

對於序列 $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.