我们定义一个集合的 \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.