E - LIS and Inversion 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 800 点

問題文

長さ 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 の最小コストを求めよ．

制約

  • 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

Score : 800 points

Problem Statement

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.

The score and cost of a permutation P=(P_1,P_2,\cdots,P_N) of (1,2,\cdots,N) are defined as follows:

  • The score of P is the length of a longest increasing subsequence of P.
  • The cost of P is the number of integers i (1 \leq i \leq N) that satisfy the following condition:
    • There are fewer than A_i integers j such that j < i and P_j > P_i.

For each k=1,2,\cdots,N, solve the following problem:

  • Find the minimum cost of a permutation P whose score is at least k.

Constraints

  • 1 \leq N \leq 250000
  • 0 \leq A_i < i
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N
A_1 A_2 \cdots A_N

Output

Print the answers for k=1,2,\cdots,N in this order.

Sample Input 1

4
0 1 2 1

Sample Output 1

0 0 1 3

For each k, a solution P is as follows:

  • k=1: If P=(4,2,1,3), then P has the score of 2 and the cost of 0.
  • k=2: If P=(4,3,1,2), then P has the score of 2 and the cost of 0.
  • k=3: If P=(4,1,2,3), then P has the score of 3 and the cost of 1.
  • k=4: If P=(1,2,3,4), then P has the score of 4 and the cost of 3.

Sample Input 2

3
0 0 0

Sample Output 2

0 0 0

Sample Input 3

5
0 1 2 3 4

Sample Output 3

0 1 2 3 4

Sample Input 4

11
0 0 2 3 4 5 3 7 8 2 10

Sample Output 4

0 0 0 1 2 3 4 5 7 8 9