Overview

This problem asks us to find the number of blocks that remain after repeatedly performing the operation “if the block on the right is taller, remove the block on the left” on a row of blocks. This can be solved in \(O(N)\) time using a monotonic stack.

Intuition

Understanding the Essence of the Operation

If we trace the behavior of one round, the cursor moves from right to left, performing: “if the block at position \(k\) is taller than the block at position \(k-1\), remove \(k-1\)”. Since removing a block causes the same block to be compared further with its left neighbor, the behavior is that a block will continue to “eat” shorter blocks to its left until it hits a block of equal or greater height.

From this, we get an important observation:

A block is removed if and only if a taller block reaches it from the right, eating all the shorter blocks in between.

In other words, “if a taller block comes immediately to the right of a block, that block will disappear.”

Properties of the Final State

Looking at the remaining blocks from left to right, their heights must be monotonically non-increasing (they do not get taller as we go right). This is because if there were adjacent remaining blocks where the right one is taller, the left one would still be removed, meaning the process is not yet finished.

Issues with the Naive Approach

If we simulate the rounds one by one exactly as described in the problem statement:

• Scanning one round takes \(O(M)\)
• The number of rounds can be \(O(N)\) in the worst case

This results in an overall time complexity of \(O(N^2)\) (up to \(10^{12}\) operations in the worst case), which will lead to TLE. Furthermore, removing elements from the middle of a list and shifting the rest is also a costly operation.

Algorithm

The property “when a taller block comes from the right, the shorter blocks on the left are eaten” can be simulated directly using a monotonic stack processed from left to right.

We iterate through the blocks from left to right and process them as follows:

1. Get the height \(h\) of the new block.
2. While the top of the stack (the block remaining immediately to the left) is shorter than \(h\), remove it from the stack (it is “eaten” by \(h\)).
3. Once the removal stops (the stack is empty, or the top element is greater than or equal to \(h\)), push \(h\) onto the stack.

This ensures that the stack is always kept in “monotonically non-increasing order of height from bottom to top”, which matches the property of the final state. Since we are reproducing the behavior of “eating the left neighbor that is shorter than itself and stopping at a height greater than or equal to itself” for each block from left to right, we obtain the same set of remaining blocks as we would after repeating the rounds.

The number of elements remaining in the stack at the end is the answer.

Concrete Example

For heights \([3, 1, 2]\):

• \(h=3\): Stack is empty \(\rightarrow\) push. Stack: [3]
• \(h=1\): Top is \(3\) (not \(3 < 1\)) \(\rightarrow\) push. Stack: [3, 1]
• \(h=2\): Top is \(1\) (\(1 < 2\)) \(\rightarrow\) pop. Next top is \(3\) (not \(3 < 2\)) \(\rightarrow\) push. Stack: [3, 2]

The remaining count is 2. Running the actual rounds yields the same result.

Complexity

• Time Complexity: \(O(N)\) — Each block is pushed onto the stack once and popped at most once, so the total number of push/pop operations is at most \(2N\).
• Space Complexity: \(O(N)\) — The size of the stack.

Implementation Points

• Since \(N \leq 10^6\) is large, fast I/O is essential. Read the entire input at once using sys.stdin.buffer.read() and split it using split().

• In Python, looking up attributes like stack.append / stack.pop inside a loop can be slow. You can speed it up by binding them to local variables like ap = stack.append and pop = stack.pop.

• The comparison must use a strict inequality: “shorter than” \(\rightarrow\) stack[-1] < h. Blocks of equal height are not removed (a block is only removed if the one to its right is strictly taller), so not including the equal sign is a requirement for correctness.

  Source Code

import sys

def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    stack = []
    ap = stack.append
    pop = stack.pop
    for i in range(1, n + 1):
        h = int(data[i])
        while stack and stack[-1] < h:
            pop()
        ap(h)
    sys.stdout.write(str(len(stack)) + "\n")

main()

---

This editorial was generated by claude4.8opus-high.