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.
