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$）的个数：
  • 满足 $j<i$ 且 $P_j>P_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 翻译