Alice has a sequence of non-negative integers $a_1, a_2, \ldots, a_n$ and defines a partitioning of the sequence into $k$ segments $(l_1, r_1), (l_2, r_2), \ldots, (l_k, r_k)$ as an $x$-beautiful partition if it satisfies:

• Each position $i$ ($1 \leq i \leq n$) belongs to exactly one segment. Specifically, there exists exactly one segment $(l_t, r_t)$ such that $l_t \leq i \leq r_t$;
• The smallest non-negative integer that does not appear in each consecutive subarray $a_{l_t}, a_{l_t+1}, \ldots, a_{r_t}$ does not exceed $x$.

Objective: Given a sequence of $n$ non-negative integers, help Alice determine, for each value $x$ ($0 \leq x \leq n - 1$), the minimum number of segments $k$ in an $x$-beautiful partition.

Input

• The first line contains an integer $n$ ($1 \leq n \leq 10^6$);
• The second line contains $n$ non-negative integers $a_i$ ($0 \leq a_i \leq 10^6$).

Output

• Print $n$ lines, each corresponding to the result of the $x$-beautiful partition with $x$ from $0$ to $n - 1$. If there is no satisfying partition, print -1.

Example

Input:

5 
2 0 1 0 3

Output:

-1 
3 
2 
2 
1

Subtasks

• Subtask 1 (20 points): $n \leq 100$.
• Subtask 2 (20 points): $n \leq 3000$.
• Subtask 3 (20 points): $n \leq 2 \times 10^5$.
• Subtask 4 (20 points): $k \leq 20$ for all $0 \leq x \leq n - 1$.
• Subtask 5 (20 points): No additional constraints.