== include(page="template/taskheader" task_id="salturi") ==
Poveste şi cerinţă...
Pe vremuri, oraşul Târgu Mureş avea $N$ turnuri de diverse înălţimi numerotate de la $1$ la $N$. Cronicile existente amintesc de faptul că cetatea a găzduit cel mai mare concurs între $N$ pitici în arta săritului din turn în turn, iar regulile competiţiei au fost următoarele:
* fiecare pitic $i$ va porni de pe turnul $i$;
* un pitic aflat pe un turn $k$ poate sări doar pe turnuri cu indici strict mai mici decât $k$;
* piticii pot sări doar pe turnuri strict mai înalte decât turnul pe care se află;
* dacă există mai multe turnuri pe care poate să sară, un pitic va sări pe turnul cu indicele cel mai mare;
* când un pitic nu mai găseşte vreun turn pe care să poată sări, el se va opri;
* scorul obţinut de fiecare pitic este egal cu numărul de turnuri pe care el le-a parcurs.
După sute de ani de la încheierea competiţiei, înălţimile turnurilor au fost uitate. Totuşi, cronicarii au consemnat scorurile pentru fiecare pitic.
Dându-se scorurile obţinute de fiecare pitic $i$ din cei $N$ pitici, să se afle înălţimile celor $N$ turnuri de pe vremuri. Se considera corectă orice soluţie pentru care, respectându-se regulile competiţiei, piticii obţin scorurile date. Dacă scorurile nu sunt valide pentru nici o configuraţie de înălţimi de turnuri, atunci se va afişa $-1$.
Se doreşte să se afle răspunsurile pentru $T$ astfel de probleme.
h2. Date de intrare
Fişierul de intrare $salturi.in$ ...
Fişierul de intrare $salturi.in$ conţine pe prima linie numărul natural $T$ reprezentând numărul de teste din fişierul de intrare. Urmează apoi $T$ teste. Fiecare test este descris pe câte două linii din fişier dupa cum urmează: pe prima linie se află numărul natural $N$ reprezentând numărul de pitici ce au participat la competiţie; pe următoarea linie se află $N$ numere naturale separate prin spaţiu cu semnificaţia că al $i$-lea număr reprezintă scorul obţinut de piticul $i$.
h2. Date de ieşire
În fişierul de ieşire $salturi.out$ ...
Fişierul de ieşire $salturi.out$ trebuie să conţină $T$ linii: pe linia $k$ se află răspunsul pentru testul $k$. Dacă există soluţie pentru testul $k$, atunci linia $k$ trebuie să conţină $N$ numere naturale separate prin spaţiu cu semnificaţia că al $i$-lea număr reprezintă înălţimea turnului $i$. Dacă nu există soluţie pentru testul al $k$-lea, atunci linia $k$ trebuie să conţină valoarea $-1$.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 <= T <= 5$.
* $1 <= N ≤ 250 000$. Suma $N$-urilor dintr-un fişier este maxim $500 000$.
* Scorurile obţinute de pitici sunt numere naturale între $1$ şi $N$.
* Înălţimile turnurilor de pe vremuri sunt numere naturale între $1$ şi $10^9^$.
* Pentru teste în valoare de $30$ de puncte, $1 <= N <= 1 000$.
* Problema va fi evaluată pe teste în valoare de $90$ de puncte.
* Exemplul va reprezenta teste în valoare de $10$ puncte "din oficiu".
h2. Exemplu
table(example). |_. salturi.in |_. salturi.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 2
5
1 1 2 1 2
4
1 3 2 1
| 3 4 2 6 3
-1
|
h3. Explicaţie
...
Se dau $T=2$ teste în fişier.
Pentru primul test, $N=5$. Dacă înălţimile turnurilor sunt $3 4 2 6 3$, piticii vor sări în felul următor:
Piticul $1$ (iniţial pe turnul $1$ de înălţime $3$) nu are unde să sară. Scorul lui va fi $1$.
Piticul $2$ (iniţial pe turnul $2$ de înălţime $4$) nu are unde să sară. Scorul lui va fi $1$.
Piticul $3$ (iniţial pe turnul $3$ de înălţime $2$) va sări pe turnul $2$ (de înălţime $4$), iar apoi nu mai are unde să sară. Scorul lui va fi $2$.
Piticul $4$ (iniţial pe turnul $4$ de înălţime $6$) nu are unde să sară. Scorul lui va fi $1$.
Piticul $5$ (iniţial pe turnul $5$ de înălţime $3$) va sări pe turnul $4$ (de înălţime $6$), iar apoi nu mai are unde să sară. Scorul lui va fi $2$.
Se obţin scorurile $1 1 2 1 2$, deci soluţia este una validă.
Se poate observa că înălţimile turnurilor nu sunt unice, aşadar pot fi afişate şi alte soluţii.
Pentru al doilea test, $N=4$. Nu se poate obţine nici o configuraţie de înălţimi de turnuri pentru care să se poată obţine scorurile date, aşadar se afişează $-1$.
== include(page="template/taskfooter" task_id="salturi") ==
