tree-rebuilder

Cerință

Pentru un arbore, $T$, cu $N$ noduri, definim $M(T) = m_0, m_1, \dots, m_{N-1}$, unde $m_i$ este distanța de la $i$ până la cel mai depărtat nod de nodul $i$.

Se dă un șir, $A$, de $N$ numere. Să se găsească un arbore $T$, astfel încât $M(T) = A$. Se garantează că există un astfel de arbore.

Date de intrare

Pe prima linie se găsește numrul $N$. Pe a doua linie se găsesc $N$ numere naturale, al $i$-lea dintre ele fiind $A_i$.

Date de ieșire

Se vor afișa $N$ numere, al $i$-lea dintre ele reprezentând tatăl nodului $i$. Dacă nodul $i$ este rădăcina arborelui, se va afișa $-1$. Dacă există mai multe soluții, se poate afișa oricare.

Restricții și precizări

• $2 \leq N \leq 200 \ 000$;
• $1 \leq A_i \le N$;
• În cadrul acestei probleme, distanța dintre două noduri este egală cu numărul de muchii de pe drumul simplu dintre aceste două noduri.
• Pentru teste în valoare de 30 de puncte, $1 \leq N \leq 7$;
• Pentru teste în valoare de alte 26 de puncte, $1 \leq N \leq 100$;

Exemplul 1

stdin

4
2 2 1 2

stdout

2 2 -1 2

Explicație

Acest exemplu descrie un arbore de tip stea, cu rădăcina în nodul 2, unde nodurile 0, 1 și 3 sunt frunze.