{"raw_statement":[{"iden":"problem statement","content":"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$.\nThe **score** and **cost** of a permutation $P=(P_1,P_2,\\cdots,P_N)$ of $(1,2,\\cdots,N)$ are defined as follows:\n\n*   The score of $P$ is the length of a longest increasing subsequence of $P$.\n*   The cost of $P$ is the number of integers $i$ ($1 \\leq i \\leq N$) that satisfy the following condition:\n    *   There are fewer than $A_i$ integers $j$ such that $j < i$ and $P_j > P_i$.\n\nFor each $k=1,2,\\cdots,N$, solve the following problem:\n\n*   Find the minimum cost of a permutation $P$ whose score is at least $k$."},{"iden":"constraints","content":"*   $1 \\leq N \\leq 250000$\n*   $0 \\leq A_i < i$\n*   All input values are integers."},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$N$\n$A_1$ $A_2$ $\\cdots$ $A_N$"},{"iden":"sample input 1","content":"4\n0 1 2 1"},{"iden":"sample output 1","content":"0 0 1 3\n\nFor each $k$, a solution $P$ is as follows:\n\n*   $k=1$: If $P=(4,2,1,3)$, then $P$ has the score of $2$ and the cost of $0$.\n*   $k=2$: If $P=(4,3,1,2)$, then $P$ has the score of $2$ and the cost of $0$.\n*   $k=3$: If $P=(4,1,2,3)$, then $P$ has the score of $3$ and the cost of $1$.\n*   $k=4$: If $P=(1,2,3,4)$, then $P$ has the score of $4$ and the cost of $3$."},{"iden":"sample input 2","content":"3\n0 0 0"},{"iden":"sample output 2","content":"0 0 0"},{"iden":"sample input 3","content":"5\n0 1 2 3 4"},{"iden":"sample output 3","content":"0 1 2 3 4"},{"iden":"sample input 4","content":"11\n0 0 2 3 4 5 3 7 8 2 10"},{"iden":"sample output 4","content":"0 0 0 1 2 3 4 5 7 8 9"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}