C - 積み木崩し 解説 /

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

配点 : 366 点

問題文

高橋君は N 個の積み木を左から右へ一列に並べています。左から i 番目の積み木の高さは H_i です。

高橋君は、この積み木の列に対して以下の手順で整理を行います。整理は複数のラウンドからなります。

1ラウンドの手順：

  1. 現在の列に含まれる積み木の個数を M とし、列の積み木を左から順に位置 1, 2, \ldots, M と番号付けする。
  2. カーソル k を M に設定する。
  3. k \geq 2 である間、以下を繰り返す：
  • 位置 k の積み木の高さが位置 k-1 の積み木の高さより大きい場合：
  • 位置 k-1 の積み木を列から取り除く。残った積み木を左から詰めて位置を振り直す。この結果、取り除かれた位置より右にあった積み木の位置番号はそれぞれ 1 減る。特に、直前まで位置 k にあった積み木は位置 k-1 に移動する。
  • k を 1 減らす。これにより、次のステップでカーソルが指す位置には、今回取り除きを引き起こした積み木が置かれている。したがって、同じ積み木がさらにその左隣と比較される。
  • そうでない場合（位置 k の積み木の高さが位置 k-1 の積み木の高さ以下の場合）：
  • 何もせず、k を 1 減らす。
  1. k < 2 となったらそのラウンドは終了する。

ラウンドの繰り返しと整理の終了：

  • そのラウンドで 1個以上 の積み木が取り除かれた場合、新たなラウンドを開始する（手順1に戻る）。
  • そのラウンドで 1個も 積み木が取り除かれなかった場合、整理は終了する。

なお、現在の列の積み木が 1 個以下の場合は、手順2で k \leq 1 となり手順3の条件 k \geq 2 を満たさないため、そのラウンドでは取り除きは発生せず、整理は終了します。

整理が終了した時点で、列に残っている積み木の個数を求めてください。

制約

  • 1 \leq N \leq 10^6
  • 1 \leq H_i \leq 10^9 (1 \leq i \leq N)
  • 入力はすべて整数である

入力

N
H_1 H_2 \ldots H_N
  • 1 行目には、積み木の個数を表す整数 N が与えられる。
  • 2 行目には、左から i 番目の積み木の高さを表す整数 H_i が、スペース区切りで N 個与えられる。

出力

整理が終了した時点で列に残っている積み木の個数を 1 行で出力せよ。

入力例 1

5
3 1 4 2 5

出力例 1

1

入力例 2

6
9 7 7 5 3 1

出力例 2

6

入力例 3

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

出力例 3

2

入力例 4

30
15 3 20 18 7 25 10 10 30 5 12 28 1 35 22 22 40 6 9 33 14 50 2 45 45 11 60 8 55 13

出力例 4

3

入力例 5

1
1000000000

出力例 5

1

Score : 366 pts

Problem Statement

Takahashi has N blocks arranged in a row from left to right. The height of the i-th block from the left is H_i.

Takahashi performs a reorganization on this row of blocks using the following procedure. The reorganization consists of multiple rounds.

Procedure of one round:

  1. Let M be the number of blocks currently in the row, and number the blocks in the row from left to right as positions 1, 2, \ldots, M.
  2. Set a cursor k to M.
  3. While k \geq 2, repeat the following:
  • If the height of the block at position k is strictly greater than the height of the block at position k-1:
  • Remove the block at position k-1 from the row. Shift the remaining blocks to the left and re-index them. As a result, the position index of each block to the right of the removed block decreases by 1. In particular, the block that was at position k just before this step moves to position k-1.
  • Decrease k by 1. As a result, in the next step, the cursor will point to the block that caused the removal in this step. Thus, the same block will be compared with its new left neighbor.
  • Otherwise (if the height of the block at position k is less than or equal to the height of the block at position k-1):
  • Do nothing, and decrease k by 1.
  1. When k < 2, the round ends.

Repetition of rounds and termination of reorganization:

  • If one or more blocks were removed during the round, start a new round (return to Step 1).
  • If no blocks were removed during the round, the reorganization ends.

Note that if there is 1 or fewer blocks in the current row, we will have k \leq 1 in Step 2, which does not satisfy the condition k \geq 2 in Step 3. Thus, no blocks will be removed in that round, and the reorganization will end.

Find the number of blocks remaining in the row when the reorganization ends.

Constraints

  • 1 \leq N \leq 10^6
  • 1 \leq H_i \leq 10^9 (1 \leq i \leq N)
  • All input values are integers.

Input

N
H_1 H_2 \ldots H_N
  • The first line contains an integer N, representing the number of blocks.
  • The second line contains N space-separated integers, where the i-th integer represents the height of the i-th block from the left, H_i.

Output

Print the number of blocks remaining in the row when the reorganization ends in a single line.

Sample Input 1

5
3 1 4 2 5

Sample Output 1

1

Sample Input 2

6
9 7 7 5 3 1

Sample Output 2

6

Sample Input 3

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

Sample Output 3

2

Sample Input 4

30
15 3 20 18 7 25 10 10 30 5 12 28 1 35 22 22 40 6 9 33 14 50 2 45 45 11 60 8 55 13

Sample Output 4

3

Sample Input 5

1
1000000000

Sample Output 5

1