Opis problemu

Definiujemy $\operatorname{mex}$ zbioru $S$ jako najmniejszą nieujemną liczbę całkowitą, która nie należy do $S$.

Dany jest ciąg $a_1, \dots, a_n$. Dla każdego $1 \leq k \leq n$ definiujemy $b_k$ w następujący sposób:

• Dla wszystkich podciągów ciągu $a$ o długości $k$ wyznaczamy $\operatorname{mex}$ zbioru liczb tworzących ten podciąg.
• Dla wszystkich wyznaczonych w ten sposób wartości $\operatorname{mex}$, wyznaczamy $\operatorname{mex}$ zbioru tych wartości i oznaczamy go jako $b_k$.

Wyznacz ciąg $b$.

Wejście

Pierwsza linia zawiera liczbę całkowitą dodatnią $n$ ($1 \leq n \leq 10^5$).

Druga linia zawiera $n$ liczb całkowitych $a_1, \dots, a_n$ ($0 \leq a_i \leq n$).

Wyjście

Wypisz $n$ liczb całkowitych $b_1, \dots, b_n$.

Przykład

Wejście 1

6
0 0 0 1 2 3

Wyjście 1

2 3 4 0 0 0