Overview

After the clean-up, the only blocks that remain are those that have “no block strictly taller than themselves to their right.”

Therefore, by iterating from right to left and counting the blocks with a height greater than or equal to the maximum height seen so far, we can find the answer.

Analysis

The condition for a block to be removed is:

The block immediately to its right is strictly taller than itself.

In other words, for a block to be removed, there must be a block originally to its right that is strictly taller than it.

Conversely, if there is no block to its right that is strictly taller than itself, that block will never be removed.
This is because a block on the left can never remove a block on its right.

On the other hand, if there is a block to its right that is strictly taller than itself, that block will eventually be removed.

For example, consider the following sequence:

4 2 4 3 5 5 1

Looking from right to left:

• 1 remains because there is nothing to its right.
• The second 5 from the right remains because it is greater than or equal to the maximum to its right (1).
• The 5 to its left also remains because there is no block strictly taller than itself to its right.
• 3, 4, 2, and 4 are removed because there is a 5 to their right.

Ultimately, the remaining blocks are:

5 5 1

The important point is that the comparison condition is “strictly greater.”
Blocks of equal height do not remove each other, so blocks with a height equal to the maximum to their right also remain.

Therefore, by iterating from right to left, we can determine:

• If the current height is greater than or equal to the maximum height seen so far, it remains.
• If the current height is strictly less than the maximum height seen so far, it is removed.

A naive simulation of removing blocks directly from the sequence would take too much time due to the deletion operations.
In particular, deleting an element from the middle of a Python list takes \(O(N)\) time, resulting in an overall time complexity of \(O(N^2)\), which will not pass within the time limit for \(N \leq 10^6\).

Algorithm

We iterate through the blocks from right to left.

Let the variable mx be the “maximum height seen so far to the right.”

For each block with height \(H_i\):

• If \(H_i \geq mx\):
  There is no block to its right strictly taller than \(H_i\), so this block remains.
  Increment the answer by \(1\) and update mx to \(H_i\).

• If \(H_i < mx\):
  There is a block to its right strictly taller than itself, so this block is removed.

By performing this check for all blocks, we can find the number of remaining blocks.

In the code, the entire input is read into data.
Since data[0] is \(N\), the actual heights are stored from data[1] to data[N].

mx = 0
ans = 0

for i in range(len(data) - 1, 0, -1):
    h = data[i]
    if h >= mx:
        ans += 1
        mx = h

Since all heights are at least \(1\), initializing mx = 0 is perfectly fine.

Complexity

• Time Complexity: \(O(N)\)
• Space Complexity: \(O(N)\)

Since the input is stored as a list, the space complexity is \(O(N)\).
The extra variables used are only mx and ans, so excluding the input, it is \(O(1)\).

Implementation Notes

The condition should be h >= mx, not h > mx.

Since blocks of equal height do not cause removal, blocks with a height equal to the maximum to their right also remain.

Source Code

import sys

data = list(map(int, sys.stdin.buffer.read().split()))
mx = 0
ans = 0

for i in range(len(data) - 1, 0, -1):
    h = data[i]
    if h >= mx:
        ans += 1
        mx = h

print(ans)

---

This editorial was generated by gpt-5.5-high.