== 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-urile 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 109.
* Pentru teste în valoare de 30 de puncte, 1 ≤ N ≤ 1 000.
* Problema va fi evaluată pe teste în valoare de 90 de puncte.
* Se vor acorda 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") ==