Universal Cup Judging System

Universal Cup

Süre Sınırı: 2.0 s Bellek Sınırı: 1024 MB Toplam puan: 100 Hack'lenebilir ✓
İstatistikler

«Ogni inizio deve avere una fine»

Per una sequenza $A = (a_1, a_2, \dots, a_m)$, definiamo:

  • la lunghezza della più lunga sottosequenza strettamente crescente: $$\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}\}$$
  • la lunghezza della più lunga sottosequenza strettamente decrescente: $$\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}\}$$

Per qualsiasi sequenza $A$, definiamo $f(A)$ come il massimo intero $k$ che soddisfa le seguenti condizioni:

Esistono $k$ numeri reali $x_1, x_2, \dots, x_k$. Dopo averli aggiunti in ordine alla fine di $A$, otteniamo una nuova sequenza $B = (a_1, a_2, \dots, a_m, x_1, x_2, \dots, x_k)$, e valgono le seguenti condizioni:

  1. Tutti gli elementi nella sequenza $B$ sono a due a due distinti;
  2. $\text{LIS}(B) = \text{LIS}(A)$;
  3. $\text{LDS}(B) = \text{LDS}(A)$.

Ora, data una permutazione $P = (P_1, P_2, \dots, P_n)$ di lunghezza $n$, per ciascun prefisso $P^{(i)} = (P_1, P_2, \dots, P_i)$, devi calcolare $f(P^{(i)})$ e stampare tutte le risposte.

«Un giorno tornerò al tuo fianco»

Input

La prima riga contiene un intero $T$ ($1 \le T \le 10^5$), che indica il numero di casi di test.

Per ciascun caso di test:

  • La prima riga contiene un intero $n$ ($1 \le n \le 2 \cdot 10^5$);
  • La seconda riga contiene $n$ interi $P_1, P_2, \dots, P_n$ ($1 \le P_i \le n$), che rappresentano una permutazione di lunghezza $n$.

È garantito che la somma di $n$ su tutti i casi di test non supera $2 \cdot 10^5$.

Output

Per ciascun caso di test, stampa una riga contenente $n$ interi che rappresentano le risposte.

Esempi

Input 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

Output 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.