findmin

Findmin

== include(page="template/taskheader" task_id="findmin") ==

Se dă un şir P de lungime N cu elemente distincte din multimea {1,2..,N}. Pentru fiecare poziţie i din şirul P se cere să aflaţi cea mai mică poziţie j,  astfel încât P[j] < P[i] şi j < i . În caz că o astfel de poziţie nu există se consideră -1 ca soluţie.

Se dă un şir $P$ de lungime $N$ cu elemente distincte din multimea ${1,2,...,N}$. Pentru fiecare poziţie $i$ din şirul $P$ se cere să aflaţi cea mai mică poziţie $j$, astfel încât $P[j] < P[i]$ şi $j < i$. În caz că o astfel de poziţie nu există se consideră $-1$ ca soluţie.

h2. Date de intrare

Fişierul de intrare $findmin.in$ conţine pe prima linie N, reprezentând lungimea şirului iar pe a doua linie N numere naturale, reprezentând elementele şirului P.

Fişierul de intrare $findmin.in$ conţine pe prima linie $N$, reprezentând lungimea şirului iar pe a doua linie $N$ numere naturale, reprezentând elementele şirului $P$.

h2. Date de ieşire

În fişierul de ieşire $findmin.out$ se vor afişa pe prima linie N numere despărţite prin câte un spaţiu, unde al i-lea număr reprezintă răspunsul pentru al i-lea element din şir.

În fişierul de ieşire $findmin.out$ se vor afişa pe prima linie $N$ numere despărţite prin câte un spaţiu, unde al $i$-lea număr reprezintă răspunsul pentru al $i$-lea element din şir.

h2. Restricţii

* $1 ≤ N ≤  10^6$
* $1 ≤ P[i] ≤  N$

* $1 ≤ N ≤ 10^6^$
* $1 ≤ P[i] ≤ N$

* $Şirul P este indexat de la 1.$
h2. Exemplu