Overview

Whether each block remains in the end is determined solely by “whether there is a taller block to its right.”
If there is no taller block to its right, it remains; otherwise, it is removed.

Observation

During the reorganization process, a block is removed only when:

• the block immediately to its right is taller than itself.

In other words, a block is always removed by “a taller block to its right.”
It is never removed by any block to its left.

The key point here is that the relative order of the blocks does not change; they are simply removed, and the remaining blocks shift to fill the gaps.

Conditions for a Block to Remain

Let’s consider the \(i\)-th block from the left.

Case 1: There is a taller block to its right

That is, when

\[ H_i < \max(H_{i+1}, H_{i+2}, \ldots, H_N) \]

holds.

In this case, the tallest block to its right will move leftward during the cleanup, removing any blocks shorter than itself.
As a result, block \(i\) will also be removed.

In fact, such blocks are removed in the very first round.

Case 2: There is no taller block to its right

That is, when

\[ H_i \geq \max(H_{i+1}, H_{i+2}, \ldots, H_N) \]

holds.

Since there is no taller block to its right, there is no block that can remove this one.
Therefore, it remains until the end.

In particular, if two blocks have the same height, one is not strictly taller than the other, so it is not removed.
Thus, the condition uses \(\geq\) rather than \(>\).

Example

For example, consider:

\[ H = [5, 2, 4, 1, 3] \]

Looking from right to left:

• \(3\) remains because there is nothing to its right.
• \(1\) is removed because there is \(3\) to its right.
• \(4\) remains because it is greater than or equal to the maximum on its right (\(3\)).
• \(2\) is removed because there is \(4\) to its right.
• \(5\) remains because it is greater than or equal to the maximum on its right (\(4\)).

Thus, the remaining blocks are:

\[ [5, 4, 3] \]

and the answer is \(3\).

Why Naive Simulation is Difficult

If we delete blocks from the sequence exactly as described in the problem, deletions will occur frequently from the middle of the sequence.

Specifically, deleting an element from the middle of a std::vector requires shifting all subsequent elements, which takes \(O(N)\) time.
Since deletions can occur up to \(N\) times, the overall time complexity can be \(O(N^2)\).

With \(N \leq 10^6\), this will result in a Time Limit Exceeded (TLE).

Therefore, instead of simulating the actual deletions, we utilize the “conditions for a block to remain.”

Algorithm

We scan the blocks from right to left while keeping track of the maximum height of the blocks seen so far.

Let the variable mx be the maximum height of the blocks to the right of the current position.

Iterating from right to left:

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

The pseudocode is as follows:

mx = -∞
ans = 0

for i = N-1 downto 0:
    if H[i] >= mx:
        ans += 1
        mx = H[i]

print(ans)

The blocks we are counting in this way are “the blocks that form the running maximum when viewed from the right.”
This is the suffix maximum, i.e., the maximum value from the back.

Complexity

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

Implementation Details

• The height \(H_i\) is at most \(10^9\), which fits in a standard int, but we use long long to be safe.

• The initial value of the maximum height on the right, mx, should be smaller than any possible block height.

  • In the code, LLONG_MIN (or a sufficiently small value) is used.

• The condition is H[i] >= mx.

  • Since blocks of the same height are not removed, we must use >= instead of >.

    Source Code

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;

    vector<long long> H(N);
    for (int i = 0; i < N; i++) cin >> H[i];

    long long mx = LLONG_MIN;
    int ans = 0;

    for (int i = N - 1; i >= 0; i--) {
        if (H[i] >= mx) {
            ans++;
            mx = H[i];
        }
    }

    cout << ans << '\n';
    return 0;
}

---

This editorial was generated by gpt-5.5-high.