Overview

This problem asks us to find the number of blocks that ultimately remain after repeatedly performing the operation “remove the block to the left if the block to its right is taller than itself” on a row of blocks.

At first glance, it seems to require a complex simulation, but by thinking “from right to left”, we can solve it with a very simple rule (a one-way scan using a stack).

Analysis

Why is a naive simulation not good enough?

If we simulate the process as described in the problem statement by scanning the array and removing elements in each round, it would take \(O(N^2)\) time in the worst case. Since \(N \le 10^6\) is very large in this problem, a naive simulation will result in a Time Limit Exceeded (TLE). Therefore, we need to find a more efficient approach.

Key Observation: “Domino Effect” from Right to Left

The operation in this problem behaves as: “a tall block on the right successively eliminates the shorter blocks to its left.”

As a concrete example, consider the case where the heights of the blocks are \(H = [3, 2, 4, 1]\).

1. The rightmost block \(1\): Since there is no block to its right, it will never be removed and is guaranteed to survive.
2. The 2nd block from the right \(4\): Since it is taller than the \(1\) to its right, it survives without being removed. Furthermore, this \(4\) has the power to successively eliminate any shorter blocks to its left (such as \(2\) and \(3\)).
3. The 3rd block from the right \(2\): Since it is shorter than the \(4\) to its right, it will eventually be swept away (removed) by \(4\).
4. The leftmost block \(3\): Since this is also shorter than the \(4\) to its right, it is similarly removed.

Thus, when looking from right to left, only blocks that are at least as tall as the “threshold height of the blocks already guaranteed to survive” can survive.

Summary of Survival Conditions

We look at the blocks from right to left. - Let the height of the current block be \(x\). - Let \(S\) be the height of the leftmost block that has been guaranteed to survive so far. - If \(x \ge S\), no block to the right can eliminate \(x\). Thus, \(x\) survives. At this point, the new threshold is updated to \(x\) (\(S \leftarrow x\)). - If \(x < S\), \(x\) will eventually be eliminated by \(S\) to its right, so it does not survive.

By applying this rule, we can identify all the blocks that will ultimately survive in a single scan from right to left.

---

Simulation with a Concrete Example

Let’s look at \(H = [3, 2, 4, 1]\) from right to left (in reverse order).

• Looking at \(1\): The stack is empty, so it is guaranteed to survive. Add it to the stack.
  • Stack: [1]
• Looking at \(4\): Since it is greater than or equal to the top of the stack (\(1\)), it is guaranteed to survive. Add it to the stack.
  • Stack: [1, 4]
• Looking at \(2\): Since it is less than the top of the stack (\(4\)), it is eliminated. Do not add it to the stack.
  • Stack: [1, 4]
• Looking at \(3\): Since it is less than the top of the stack (\(4\)), it is eliminated. Do not add it to the stack.
  • Stack: [1, 4]

Ultimately, [1, 4] (2 blocks) remain in the stack, which is the answer.

Algorithm

We can solve this using a stack (a list in Python) with the following steps:

1. Prepare an empty stack stack.
2. Scan the input array \(H\) in reverse order, from the end (rightmost) to the beginning (leftmost).
3. For each element \(x\):
   • If stack is empty, or the top element of stack is less than or equal to \(x\):
     • Push \(x\) onto stack.
   • Otherwise (if \(x\) is strictly less than the top element of stack):
     • Do nothing (ignore it).
4. Output the size (length) of the final stack.

Complexity

• Time Complexity: \(O(N)\) Since we scan the array in reverse order exactly once, the process runs in linear time with respect to the number of elements \(N\). Even for \(N = 10^6\), it runs very fast in less than 0.1 seconds.
• Space Complexity: \(O(N)\) This is for storing the input data and, in the worst case (e.g., when all blocks survive), holding up to \(N\) elements in the stack.

Implementation Points

• Fast I/O: When processing inputs of size \(N = 10^6\) in Python, repeatedly calling input() can cause an I/O bottleneck and lead to TLE. We can speed it up by reading all inputs at once using sys.stdin.read().split().

• Scanning in Reverse: By using reversed(H), we can efficiently iterate through the elements from the back without modifying the original array.

  Source Code

import sys


def solve():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    N = int(input_data[0])
    H = [int(x) for x in input_data[1:]]

    stack = []
    for x in reversed(H):
        if not stack or stack[-1] <= x:
            stack.append(x)

    print(len(stack))


if __name__ == "__main__":
    solve()

---

This editorial was generated by gemini-3.5-flash-high.