Problem Description

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

Given a sequence $a_1,\dots,a_n$, for each $1\leq k\leq n$, we define $b_k$ in the following way:

• For all subarrays of $a$ with length $k$, compute the $\operatorname{mex}$ of the set of numbers in that subarray.
• For the set of all computed $\operatorname{mex}$ values, compute the $\operatorname{mex}$ of this set, and denote it as $b_k$.

You are asked to output the sequence $b$.

Input Format

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

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

Output Format

Output $n$ integers $b_1,\dots,b_n$ in one line.

6
0 0 0 1 2 3

2 3 4 0 0 0

Hint

Problem Usage Agreement

From the THUPC2024 (Tsinghua University Student Programming Contest and Collegiate Invitational Contest 2024) preliminary round.

The following "this repository" all refer to the THUPC2024 preliminary round official repository (https://github.com/ckw20/thupc2024_pre_public).

1. Any organization or individual may use or repost the problems in this repository for free.

2. When using the problems in this repository, any organization or individual should do so for free and publicly. It is strictly forbidden to use these problems for profit or to add special access permissions to these problems.

3. If possible, when using the problems in this repository, please also provide ways to obtain resources such as testdata, reference solutions, and editorials. Otherwise, please attach the GitHub link of this repository.

Translated by ChatGPT 5