Negotiable

Task

We denote by $\text{MEX}$ of a sequence of numbers the smallest non-negative integer that does not belong to the sequence. For example, $\text{MEX}(0, 4, 4, 1, 2) = 3$ and $\text{MEX}(1, 2, 3) = 0$.

We call a sequence $b$ of numbers $b_1, b_2, \ldots, b_K$ $\text{x-negotiable}$ if and only if $\text{MEX}(b_1, b_2,\dots,b_K) \leq x$.

For a given sequence $b$ of length $K$, consider a sequence of indices $1 \leq i_1 < i_2 < \ldots < i_s < K$. This sequence determines a division of $b$ into $s+1$ consecutive subsequences: $(b_{1}, b_2, \ldots, b_{i_1})$, $(b_{i_1+1}, b_{i_1+2}, \ldots, b_{i_2})$, $\ldots$, $(b_{i_s+1}, b_{i_s+2}, \ldots, b_K)$. We call this division an $\textit{x-malleable partition}$ if and only if each of the $s+1$ subsequences is $x$-negotiable. We define the size of the partition as the number of subsequences, that is, $s + 1$.

You are given a sequence $a$ of $N$ non-negative integers. Determine, for each value of $x$ from $1$ to $N$, the minimum size of an $x$-malleable partition of sequence $a$.

Input Data

The first line contains the integer $N$.
The second line contains $N$ integers — the elements of sequence $A$.

Output data

Print $N$ integers, separated by spaces, representing the answer for each $x$.

Restrictions

• $1 \leq N \leq 1\,000\,000$.
• $0 \leq a_i \leq N$.

Local minima are defined as values $v_i$ with $2 \le i \le N - 1$ such that $v_{i-1} \ge v_i \le v_{i+1}$. Local maxima are defined as values $v_i$ with $2 \le i \le N - 1$ such that $v_{i-1} \le v_i \ge v_{i+1}$.

Example

stdin

5
0 1 2 3 0

stdout

3 2 2 11 

Explanation

For $x = 1$, an optimal partition is $[1, 1], [2, 3], [4, 5]$.
For $x = 2$, an optimal partition is $[1, 2], [3, 5]$.
For $x = 3$, an optimal partition is $[1, 3], [4, 5]$.
For $x = 4$, an optimal partition is $[1, 5]$.
For $x = 5$, an optimal partition is $[1, 5]$.