AT_arc180_e [ARC180E] LIS and Inversion

给定一个长度为 $N$ 的整数序列 $A=(A_1,A_2,\cdots,A_N)$。这里，保证对于每个 $i$，有 $0\leq A_i < i$。 对于 $(1,2,\cdots,N)$ 的一个排列 $P=(P_1,P_2,\cdots,P_N)$，定义其**分数**和**代价**如下： - $P$ 的分数为 $P$ 的最长递增子序列的长度。 - $P$ 的代价为满足以下条件的整数 $i$（$1\leq i\leq N$）的个数： - 满足 $jP_i$ 的整数 $j$ 的个数小于 $A_i$。 对于每个 $k=1,2,\cdots,N$，请解决下列问题： - 求分数至少为 $k$ 的排列 $P$ 的最小代价。

输入以如下格式从标准输入读入： > $N$ $A_1$ $A_2$ $\cdots$ $A_N$

请按顺序输出 $k=1,2,\cdots,N$ 的答案。

### 限制条件 - $1\leq N\leq 250000$ - $0\leq A_i < i$ - 输入的所有值均为整数 ### 样例解释 1 对于每个 $k$，满足条件的 $P$ 如下： - $k=1$：取 $P=(4,2,1,3)$，此时 $P$ 的分数为 $2$，代价为 $0$。 - $k=2$：取 $P=(4,3,1,2)$，此时 $P$ 的分数为 $2$，代价为 $0$。 - $k=3$：取 $P=(4,1,2,3)$，此时 $P$ 的分数为 $3$，代价为 $1$。 - $k=4$：取 $P=(1,2,3,4)$，此时 $P$ 的分数为 $4$，代价为 $3$。 由 ChatGPT 4.1 翻译