E - カードの山 解説 /

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

配点 : 466 点

問題文

高橋君はカードゲームの片付けをしています。テーブルの上に N 枚のカードが左から右に一列に並んでおり、左から i 番目のカードを「カード i」と呼びます。カード i には整数 A_i が書かれています。

高橋君はこれらのカードをいくつかの山に分けて整理します。山の作り方には以下のルールがあります：

  • カード 1, カード 2, \ldots, カード N をこの順番で 1 枚ずつ処理する（順番を入れ替えることはできない）。
  • 各カードについて、次のいずれかの操作を選ぶ：
  • 新しい山を作り、そのカードを置く。
  • 既に存在するいずれかの山の一番上に、そのカードを重ねる。ただし、その山の現在の一番上のカードに書かれた数値を x、これから重ねるカードに書かれた数値を y としたとき、x \geq y でなければならない。

このルールにより、各山ではカードに書かれた数値が下から上に向かって単調非増加になります。

高橋君はできるだけ少ない数の山にまとめたいと考えています。

さらに、高橋君は各カードについて「そのカードの直下にあるカードはどれか」も記録したいと考えています。カード i の直下のカードとは、カード i を既存の山に重ねた場合に、その時点でその山の一番上にあったカードのことを指します。カード i が新しい山を作って置かれた場合（すなわち山の一番下にある場合）、直下のカードは存在しません。

各カード i（i = 1, 2, \ldots, N）について、値 B_i を次のように定めます：

  • カード i の直下のカードが存在しない場合（山の一番下にある場合）、B_i = 0 とする。
  • カード i の直下のカードがカード j である場合、B_i = j とする。

山の数を最小にするすべての積み方を考えたとき、その中で B_1 + B_2 + \cdots + B_N が最大となるような積み方を一つ求めてください。

山の数の最小値を K として、K と B_1, B_2, \ldots, B_N を出力してください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq A_i \leq 10^9（1 \leq i \leq N）
  • 入力はすべて整数である。

入力

N
A_1 A_2 \cdots A_N
  • 1 行目には、カードの枚数を表す整数 N が与えられる。
  • 2 行目には、各カードに書かれた数値を表す N 個の整数 A_1, A_2, \ldots, A_N がスペース区切りで与えられる。

出力

K
B_1 B_2 \cdots B_N
  • 1 行目には、山の数の最小値 K を出力せよ。
  • 2 行目には、山の数が最小であるすべての積み方の中で B_1 + B_2 + \cdots + B_N が最大となる積み方における B_1, B_2, \ldots, B_N をスペース区切りで出力せよ。該当する積み方が複数ある場合は、そのうちどれを出力してもよい。

入力例 1

5
3 1 4 2 2

出力例 1

2
0 1 0 3 4

入力例 2

4
1 2 3 4

出力例 2

4
0 0 0 0

入力例 3

12
5 3 4 4 2 6 1 5 5 3 2 7

出力例 3

4
0 0 1 3 4 0 5 6 8 9 10 0

入力例 4

30
10 20 15 15 30 25 5 18 18 17 40 35 34 10 9 50 45 45 44 1 60 59 20 19 70 2 2 80 79 78

出力例 4

8
0 0 2 3 0 5 4 6 8 9 0 11 12 13 14 0 16 17 18 19 0 21 22 23 0 25 26 0 28 29

入力例 5

1
1000000000

出力例 5

1
0

Score : 466 pts

Problem Statement

Takahashi is cleaning up a card game. There are N cards lined up in a row from left to right on a table. The i-th card from the left is called "card i". Card i has an integer A_i written on it.

Takahashi will organize these cards by dividing them into several piles. The piles must be created according to the following rules:

  • Process card 1, card 2, \ldots, card N in this order, one by one (the order cannot be changed).
  • For each card, choose one of the following operations:
  • Create a new pile and place the card on it.
  • Place the card on top of an already existing pile. However, if the number written on the current top card of that pile is x and the number on the card to be placed is y, then x \geq y must hold.

Under these rules, the numbers written on the cards in each pile will be monotonically non-increasing from bottom to top.

Takahashi wants to minimize the number of piles.

Furthermore, for each card, Takahashi wants to record "which card is directly below it". The card directly below card i refers to the card that was at the top of the pile at the moment card i was placed on top of that existing pile. If card i was placed to start a new pile (i.e., it is at the bottom of the pile), there is no card directly below it.

For each card i (i = 1, 2, \ldots, N), we define the value B_i as follows:

  • If there is no card directly below card i (i.e., it is at the bottom of a pile), B_i = 0.
  • If the card directly below card i is card j, B_i = j.

Among all ways of piling the cards that minimize the number of piles, find one way that maximizes B_1 + B_2 + \cdots + B_N.

Let K be the minimum number of piles. Output K and B_1, B_2, \ldots, B_N.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq A_i \leq 10^9 (1 \leq i \leq N)
  • All input values are integers.

Input

N
A_1 A_2 \cdots A_N
  • The first line contains an integer N, representing the number of cards.
  • The second line contains N space-separated integers A_1, A_2, \ldots, A_N, representing the numbers written on the cards.

Output

K
B_1 B_2 \cdots B_N
  • In the first line, output the minimum number of piles K.
  • In the second line, output B_1, B_2, \ldots, B_N separated by spaces, representing a way of piling that maximizes B_1 + B_2 + \cdots + B_N among all ways that minimize the number of piles. If there are multiple such ways, you may output any of them.

Sample Input 1

5
3 1 4 2 2

Sample Output 1

2
0 1 0 3 4

Sample Input 2

4
1 2 3 4

Sample Output 2

4
0 0 0 0

Sample Input 3

12
5 3 4 4 2 6 1 5 5 3 2 7

Sample Output 3

4
0 0 1 3 4 0 5 6 8 9 10 0

Sample Input 4

30
10 20 15 15 30 25 5 18 18 17 40 35 34 10 9 50 45 45 44 1 60 59 20 19 70 2 2 80 79 78

Sample Output 4

8
0 0 2 3 0 5 4 6 8 9 0 11 12 13 14 0 16 17 18 19 0 21 22 23 0 25 26 0 28 29

Sample Input 5

1
1000000000

Sample Output 5

1
0