C - Dominoes Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 366 点

問題文

高橋君は N 個のドミノを一列に並べている。左から順に 1, 2, \ldots, N と番号が付けられており、各ドミノ i には「高さ」を表す正整数 A_i が定められている。

この世界のドミノ倒しでは、倒れたドミノはすぐ右隣のまだ立っているドミノに衝突し、相手の高さが自分より真に小さければ、そのドミノも倒してしまう。具体的には、連鎖は以下のルールに従って進む。

  • ドミノ i が倒れたとき、まだ倒れていないドミノのうち、i より右にあり番号が最も小さいもの（すなわち、ドミノ i のすぐ右隣にあるまだ倒れていないドミノ）をドミノ j とする。
  • そのようなドミノ j が存在し、かつ A_j < A_i（ドミノ j の高さがドミノ i の高さより真に小さい）ならば、ドミノ i がドミノ j を倒す。続いて、新たに倒れたドミノ j を起点として同じルールを適用する。すなわち、次はドミノ j の高さ A_j を基準にして、さらに右隣のまだ倒れていないドミノを倒せるか判定する。
  • ドミノ i より右にまだ倒れていないドミノが存在しない場合、またはドミノ j の高さがドミノ i の高さ以上（A_j \geq A_i）である場合、連鎖はそこで止まる。

高橋君はドミノ 1, 2, \ldots, N の順に、まだ倒れていなければ指で倒す操作を行う。既に倒れている場合は何もせず次のドミノに進む。指で倒した場合、そのドミノを起点として上記の連鎖ルールが適用される。

すべてのドミノが倒れた後、各ドミノ i（1 \leq i \leq N）について、ドミノ i を倒した直接の原因を求めてください。ドミノ i が別のドミノ k の連鎖によって倒された場合（上記ルールにおいてドミノ k が倒れた直後にドミノ i が倒された場合）は、そのドミノの番号 k を出力してください。高橋君が指で直接倒した場合は 0 を出力してください。

制約

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

入力

N
A_1 A_2 \ldots A_N
  • 1 行目には、ドミノの個数を表す整数 N が与えられる。
  • 2 行目には、各ドミノの高さを表す N 個の整数 A_1, A_2, \ldots, A_N がスペース区切りで与えられる。

出力

N 個の整数をスペース区切りで 1 行に出力せよ。i 番目の整数は、ドミノ i を倒した直接の原因となったドミノの番号（高橋君が直接倒した場合は 0）である。

入力例 1

5
5 3 4 2 1

出力例 1

0 1 0 3 4

入力例 2

3
2 2 1

出力例 2

0 0 2

入力例 3

12
10 7 6 8 5 4 9 3 3 2 11 1

出力例 3

0 1 2 0 4 5 0 7 0 9 0 11

入力例 4

30
100 90 80 85 70 60 50 75 74 73 20 21 19 18 200 150 160 140 130 120 110 111 109 108 50 49 48 47 46 45

出力例 4

0 1 2 0 4 5 6 0 8 9 10 0 12 13 0 15 0 17 18 19 20 0 22 23 24 25 26 27 28 29

入力例 5

1
1000000000

出力例 5

0

Score : 366 pts

Problem Statement

Takahashi has lined up N dominoes in a row. They are numbered 1, 2, \ldots, N from left to right, and each domino i has a positive integer A_i representing its "height."

In this world's domino toppling, a fallen domino collides with the nearest still-standing domino immediately to its right, and if the other domino's height is strictly less than its own, it knocks that domino down as well. Specifically, the chain proceeds according to the following rules:

  • When domino i falls, let domino j be the domino that is to the right of i with the smallest number among those that have not yet fallen (i.e., the nearest still-standing domino immediately to the right of domino i).
  • If such a domino j exists and A_j < A_i (the height of domino j is strictly less than the height of domino i), then domino i knocks down domino j. Subsequently, the same rule is applied starting from the newly fallen domino j. That is, using domino j's height A_j as the reference, it is determined whether the next still-standing domino to the right can be knocked down.
  • If there is no still-standing domino to the right of domino i, or if the height of domino j is greater than or equal to the height of domino i (A_j \geq A_i), the chain stops there.

Takahashi performs the operation of pushing down dominoes with his finger in the order 1, 2, \ldots, N, pushing each one only if it has not yet fallen. If it has already fallen, he does nothing and moves on to the next domino. When he pushes a domino with his finger, the chain rule described above is applied starting from that domino.

After all dominoes have fallen, for each domino i (1 \leq i \leq N), determine the direct cause of domino i falling. If domino i was knocked down by the chain from another domino k (i.e., domino i fell immediately after domino k fell according to the above rules), output that domino's number k. If Takahashi directly pushed it down with his finger, output 0.

Constraints

  • 1 \leq N \leq 5 \times 10^5
  • 1 \leq A_i \leq 10^9
  • All inputs are integers.

Input

N
A_1 A_2 \ldots A_N
  • The first line contains an integer N representing the number of dominoes.
  • The second line contains N integers A_1, A_2, \ldots, A_N separated by spaces, representing the height of each domino.

Output

Output N integers separated by spaces on a single line. The i-th integer is the number of the domino that directly caused domino i to fall (or 0 if Takahashi directly pushed it down).

Sample Input 1

5
5 3 4 2 1

Sample Output 1

0 1 0 3 4

Sample Input 2

3
2 2 1

Sample Output 2

0 0 2

Sample Input 3

12
10 7 6 8 5 4 9 3 3 2 11 1

Sample Output 3

0 1 2 0 4 5 0 7 0 9 0 11

Sample Input 4

30
100 90 80 85 70 60 50 75 74 73 20 21 19 18 200 150 160 140 130 120 110 111 109 108 50 49 48 47 46 45

Sample Output 4

0 1 2 0 4 5 6 0 8 9 10 0 12 13 0 15 0 17 18 19 20 0 22 23 24 25 26 27 28 29

Sample Input 5

1
1000000000

Sample Output 5

0