Seta tworzy zadania na CCO! Wymyśliła następujący problem:

Mając daną tablicę $A[1, \dots, N]$, której wartości mieszczą się w zakresie $[1, N]$, zdefiniujmy $B[i]$ jako liczbę par $(\ell, r)$ takich, że $\ell \le i \le r$ oraz $$A[i] = \min(A[\ell], A[\ell + 1], \dots, A[r - 1], A[r]).$$

Wypisz tablicę $B[1, \dots, N]$.

Jednak dzień przed CCO komputer Sety uległ awarii i udało jej się odzyskać tylko pliki wyjściowe. Mając daną tablicę wyjściową $B[1, \dots, N]$, czy potrafisz napisać program, który odtworzy tablicę wejściową $A[1, \dots, N]$?

Seta przypomina, że tablica $A$ nie musi być unikalna i zaakceptuje każdą poprawną tablicę.

Wejście

Pierwsza linia wejścia zawiera pojedynczą liczbę całkowitą $N$. Druga linia wejścia zawiera $N$ liczb całkowitych oddzielonych spacjami $B[1], \dots, B[N]$ ($1 \le B[i] \le N^2$).

Poniższa tabela przedstawia podział 25 dostępnych punktów:

Wyjście

Wypisz $N$ liczb całkowitych oddzielonych spacjami, tablicę $A[1], \dots, A[N]$, gdzie $1 \le A[i] \le N$. Gwarantuje się, że zawsze istnieje co najmniej jedna poprawna tablica $A$.

Jeśli istnieje więcej niż jedna poprawna tablica, możesz wypisać dowolną z nich. W szczególności, nawet jeśli oryginalna tablica $A$ była permutacją, twoja odpowiedź nie musi być permutacją.

Przykład

Wejście 1

3
3 1 2

Wyjście 1

1 3 2

Uwagi 1

• Podtablice $[1, 3, 2]$, $[1, 3]$, $[1]$ mają minimum $1$. Istnieją $3$ takie podtablice.
• Podtablica $[3]$ ma minimum $3$. Istnieje $1$ taka podtablica.
• Podtablice $[3, 2]$ oraz $[2]$ mają minimum $2$. Istnieją $2$ takie podtablice.

Wejście 2

2
2 2

Wyjście 2

1 1

Wejście 3

3
1 4 1

Wyjście 3

2 1 3

Uwagi 3

Zauważ, że $A = [2, 1, 2]$ również zostałoby zaakceptowane przez system sprawdzający.