Seta crée des problèmes pour le CCO ! Elle a imaginé le problème suivant :

Étant donné un tableau $A[1, \dots, N]$ dont les valeurs sont dans l'intervalle $[1, N]$, on définit $B[i]$ comme le nombre de paires $(\ell, r)$ telles que $\ell \le i \le r$ et $$A[i] = \min(A[\ell], A[\ell+1], \dots, A[r-1], A[r]).$$

Affichez le tableau $B[1, \dots, N]$.

Cependant, la veille du CCO, l'ordinateur de Seta a planté et elle n'a pu récupérer que les fichiers de sortie. Étant donné le tableau de sortie $B[1, \dots, N]$, pouvez-vous écrire un programme pour reconstruire le tableau d'entrée $A[1, \dots, N]$ ?

Seta vous rappelle que le tableau $A$ n'est pas nécessairement unique, et elle acceptera tout tableau valide.

Entrée

La première ligne de l'entrée contiendra un entier unique, $N$. La deuxième ligne de l'entrée contiendra $N$ entiers séparés par des espaces $B[1], \dots, B[N]$ ($1 \le B[i] \le N^2$).

Le tableau suivant montre comment les 25 points disponibles sont répartis :

Sortie

Affichez $N$ entiers séparés par des espaces, le tableau $A[1], \dots, A[N]$, où $1 \le A[i] \le N$. Il est garanti qu'il existe toujours au moins un tableau $A$ valide.

S'il existe plus d'un tableau valide, vous pouvez afficher n'importe quel tableau valide. En particulier, même si le tableau original $A$ est une permutation, votre réponse n'a pas besoin d'être une permutation.

Exemples

Exemples 1

3
3 1 2

1 3 2

Remarque 1

• Les sous-tableaux $[1, 3, 2]$, $[1, 3]$, $[1]$ ont pour minimum $1$. Il y a 3 tels sous-tableaux.
• Le sous-tableau $[3]$ a pour minimum $3$. Il y a 1 tel sous-tableau.
• Les sous-tableaux $[3, 2]$ et $[2]$ ont pour minimum $2$. Il y a 2 tels sous-tableaux.

Exemples 2

2
2 2

1 1

Exemples 3

3
1 4 1

2 1 3

Remarque 3

Notez que $A = [2, 1, 2]$ serait également accepté par le juge.