我们定义一个集合的 $\operatorname{mex}$ 是最小的不在 $S$ 中的非负整数。

给定一个序列 $a_1,\dots,a_n$，对于每个 $1\leq k\leq n$，我们按照如下方式定义 $b_k$：

• 对于 $a$ 的所有长为 $k$ 的子区间，求出这个子区间构成的数集的 $\operatorname{mex}$。
• 对于求出的所有 $\operatorname{mex}$，求出这个数集自己的 $\operatorname{mex}$，记为 $b_k$。

请你求出序列 $b$。

We define $\operatorname{mex}$ of a set $S$ to be the smallest non-negative integer not in $S$.

Given a sequence $a_1,\dots,a_n$, for each $1\leq k\leq n$, we define $b_k$ as follows:

• For all subintervals of $a$ of length $k$, find the $\operatorname{mex}$ of the set of numbers formed by this subinterval.
• For all $\operatorname{mex}$ found, find $\operatorname{mex}$ of the set of numbers itself, denoted $b_k$.

Find the sequence $b$.

第一行输入一个正整数 $n$（$1\leq n\leq 10^5$）。

第二行输入 $n$ 个整数 $a_1,\dots,a_n$（$0\leq a_i\leq n$）。

The first line enters a positive integer $n$ ($1\leq n\leq 10^5$).

The second line enters $n$ integers $a_1,\dots,a_n$ ($0\leq a_i\leq n$).

一行输出 $n$ 个整数 $b_1,\dots,b_n$。

A line outputs $n$ integers $b_1,\dots,b_n$.