Subiectul II

Comentează, în minimum 50 de cuvinte, textul de mai jos, evidențiind relația dintre ideea poetică și mijloacele artistice folosite.

Se dă o permutare $p_1, \dots , p_N$ a mulțimii $\{1, 2, \dots, N \}$. Un element $p_j$ se numește critic pentru elementul $p_i$ dacă $j > i$ și elementul $p_j$ apare în toate subșirurile crescătoare de lungime maximă care încep cu elementul $p_i$.

Cerință

Pentru fiecare $1 ≤ i ≤ N$ , aflați câte elemente $p_j$ sunt critice pentru elementul $p_i$.

Date de intrare

Pe prima linie a intrării se va găsi un singur număr întreg $N$. Pe a doua linie a intrării se vor găsi cele $N$ elemente ale permutării.

Date de ieșire

Pe prima linie a ieșirii se vor găsi $N$ numere naturale, fiecare reprezentând numărul elementelor critice pentru fiecare poziție $i \ (1 ≤ i ≤ N )$.

Restricții și precizări

• $1 \leq N \leq 1 \ 000 \ 000$

Exemplu

stdin

5
3 5 1 2 4

stdout

0 0 2 1 0

Explicație

• Pentru elementul $3$, subșirurile crescătoare de lungime maximă sunt $(3, 5)$ respectiv $(3, 4)$. Observăm că niciun element (mai puțin $3$) nu apare în toate.
• Pentru elementul $5$, subșirul unic de lungime maximă este $(5)$. Niciun element (mai puțin $5$) nu apare în șir.
• Pentru elementul $1$, subșirul unic de lungime maximă este $(1, 2, 4)$. În acest șir apar (în afară de $1$) elementele $2$ și $4$.
• Pentru elementul $2$, subșirul unic de lungime maximă este $(2, 4)$. În acest șir apare (în afară de $2$) elementul $4$.
• Pentru elementul $4$, subșirul unic de lungime maximă este $(4)$. Niciun element (mai puțin $4$) nu apare în șir.