分数: 800 点
问题陈述
给你一个整数序列 A=(A_1,A_2,\cdots,A_N) 长度 N。 在此,可以保证 0 \leq A_i < i 对于每个 i.
的 分数 $$$v$$$ 的 和 成本 的排列 P=(P_1,P_2,\cdots,P_N) of (1,2,\cdots,N) 定义如下:
- 的分数 P 是最长递增子序列的长度 P.
- 的成本 P 是整数的个数 i (1 \leq i \leq N) 满足以下条件:
- 少于 A_i 整数 j 这样 j < i 和 P_j > P_i.
对于每个 k=1,2,\cdots,N,解决以下问题:
- 找到排列的最小成本 P 其分数至少为 k.
约束
- 1 \leq N \leq 250000
- 0 \leq A_i < i
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N A_1 A_2 \cdots A_N
输出
打印以下问题的答案 k=1,2,\cdots,N 按此顺序。
示例输入 1
4 0 1 2 1
示例输出 1
0 0 1 3
对于每个 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.
示例输入 2
3 0 0 0
示例输出 2
0 0 0
示例输入 3
5 0 1 2 3 4
示例输出 3
0 1 2 3 4
示例输入 4
11 0 0 2 3 4 5 3 7 8 2 10
示例输出 4
0 0 0 1 2 3 4 5 7 8 9