Seta está creando problemas para la CCO. Se le ocurrió el siguiente problema:

Dado un arreglo $A[1, \dots, N]$ cuyos valores están en el rango $[1, N]$, definimos $B[i]$ como el número de pares $(\ell, r)$ tales que $\ell \leq i \leq r$ y $$A[i] = \min(A[\ell], A[\ell+1], \dots, A[r-1], A[r]).$$

Imprime el arreglo $B[1, \dots, N]$.

Sin embargo, el día anterior a la CCO, la computadora de Seta falló y solo pudo recuperar los archivos de salida. Dado el arreglo de salida $B[1, \dots, N]$, ¿puedes escribir un programa para reconstruir el arreglo de entrada $A[1, \dots, N]$?

Seta te recuerda que el arreglo $A$ no es necesariamente único, y aceptará cualquier arreglo válido.

Entrada

La primera línea de la entrada contendrá un solo entero, $N$. La segunda línea de la entrada contendrá $N$ enteros separados por espacios $B[1], \dots, B[N]$ ($1 \leq B[i] \leq N^2$).

La siguiente tabla muestra cómo se distribuyen los 25 puntos disponibles:

Salida

Imprime $N$ enteros separados por espacios, el arreglo $A[1], \dots, A[N]$, donde $1 \leq A[i] \leq N$. Se garantiza que siempre existirá al menos un arreglo válido $A$.

Si hay más de un arreglo válido, puedes imprimir cualquier arreglo válido. En particular, incluso si el arreglo original $A$ es una permutación, tu respuesta no tiene por qué ser una permutación.

Ejemplos

Entrada 1

3
3 1 2

Salida 1

1 3 2

Nota 1

• Los subarreglos $[1, 3, 2]$, $[1, 3]$, $[1]$ tienen como mínimo $1$. Hay $3$ subarreglos de este tipo.
• El subarreglo $[3]$ tiene como mínimo $3$. Hay $1$ subarreglo de este tipo.
• Los subarreglos $[3, 2]$ y $[2]$ tienen como mínimo $2$. Hay $2$ subarreglos de este tipo.

Entrada 2

2
2 2

Salida 2

1 1

Entrada 3

3
1 4 1

Salida 3

2 1 3

Nota 3

Ten en cuenta que $A = [2, 1, 2]$ también sería aceptado por el juez.