← 返回题目列表

AtCoder · arc180_e

E. LIS 和反演

中文机器翻译题面 查看原题

分数: 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