Problem Statement

You are given an integer sequence $A=(A_1,A_2,\cdots,A_N)$ of length $N$. Here, it is guaranteed that $0 \leq A_i < i$ for each $i$.

The score and cost of a permutation $P=(P_1,P_2,\cdots,P_N)$ of $(1,2,\cdots,N)$ are defined as follows:

• The score of $P$ is the length of a longest increasing subsequence of $P$.
• The cost of $P$ is the number of integers $i$ ($1 \leq i \leq N$) that satisfy the following condition:
• There are fewer than $A_i$ integers $j$ such that $j < i$ and $P_j > P_i$.

For each $k=1,2,\cdots,N$, solve the following problem:

• Find the minimum cost of a permutation $P$ whose score is at least $k$.

Constraints

• $1 \leq N \leq 250000$
• $0 \leq A_i < i$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

N
A_1 A_2 \cdots A_N

Output

Print the answers for $k=1,2,\cdots,N$ in this order.