The $\operatorname{mex}$ of a set $S$ is defined as the smallest non-negative integer not present 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 subsegments of $a$ with length $k$, calculate the $\operatorname{mex}$ of the set of numbers contained in that subsegment.
- Calculate the $\operatorname{mex}$ of the set of all $\operatorname{mex}$ values obtained in the previous step, and denote this as $b_k$.
Please find the sequence $b$.
Input
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
Output $n$ integers $b_1, \dots, b_n$ on a single line.
Examples
Input 1
6 0 0 0 1 2 3
Output 1
2 3 4 0 0 0