$\operatorname{mex}$ множества определяется как наименьшее неотрицательное целое число, не входящее в это множество $S$.

Дан массив $a_1, \dots, a_n$. Для каждого $1 \leq k \leq n$ определим $b_k$ следующим образом:

• Для всех подмассивов длины $k$ массива $a$ вычислим $\operatorname{mex}$ множества чисел, содержащихся в этом подмассиве.
• Для всех полученных значений $\operatorname{mex}$ вычислим $\operatorname{mex}$ множества этих значений, результат обозначим как $b_k$.

Найдите последовательность $b$.

Входные данные

Первая строка содержит целое положительное число $n$ ($1 \leq n \leq 10^5$).

Вторая строка содержит $n$ целых чисел $a_1, \dots, a_n$ ($0 \leq a_i \leq n$).

Выходные данные

Выведите $n$ целых чисел $b_1, \dots, b_n$.

Примеры

Пример 1

Входные данные

6
0 0 0 1 2 3

Выходные данные

2 3 4 0 0 0