問題説明

集合 $S$ の $\operatorname{mex}$ を、$S$ に含まれない最小の非負整数と定義します。

長さ $n$ の数列 $a_1, \dots, a_n$ が与えられます。各 $1 \leq k \leq n$ に対して、$b_k$ を以下のように定義します。

• $a$ の長さ $k$ のすべての連続部分列を考え、それぞれの部分列に含まれる要素の集合の $\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

出力 1

2 3 4 0 0 0