Overview

This problem asks you to look at mountains from front to back, and output only the mountains that update the “highest elevation seen so far” as “visible mountains.”

Analysis

The condition for mountain \(i\) to be visible is that “all mountains before \(i\) have elevations less than \(H_i\).”
In other words, if we let \(M=\max(H_1,\dots,H_{i-1})\) be the maximum elevation among the preceding mountains, then mountain \(i\) is visible only when \(H_i > M\) (note that even when the height is the same, \(H_i = M\), the mountain is hidden and not visible).

Why the naive approach is too slow

If we compute \(\max(H_1,\dots,H_{i-1})\) from scratch for each \(i\), finding the maximum takes \(O(i)\), resulting in a total of
\(O(1+2+\cdots+(N-1)) = O(N^2)\).
Since \(N \le 2\times 10^5\), \(O(N^2)\) is too slow.

Solution strategy

By incrementally updating the “maximum elevation so far,” we can determine visibility by examining each mountain only once.
Specifically, we process mountains from left to right: - If a mountain is taller than the current maximum max_h → it is visible → add it to the answer and update max_h - Otherwise → it is not visible → do nothing

Concrete example

For \(H = [3, 2, 5, 5, 6]\): - 1st mountain, 3: greater than max_h=-1 → visible (max_h=3) - 2nd mountain, 2: less than max_h=3 → not visible - 3rd mountain, 5: greater than max_h=3 → visible (max_h=5) - 4th mountain, 5: equal to max_h=5 → not visible (same height means hidden) - 5th mountain, 6: greater than max_h=5 → visible (max_h=6)
Therefore the answer is 1 3 5.

Algorithm

1. Initialize max_h to a sufficiently small value (e.g., -1).
2. Examine mountains from front to back (from \(i=1\) to \(N\)).
3. If \(H_i > max_h\), then mountain \(i\) is visible, so add \(i\) to the answer and update max_h = H_i.
4. Finally, output the mountain numbers in order.

With this approach, we only need to remember the “maximum elevation so far,” and each mountain can be checked in \(O(1)\).

Complexity

• Time complexity: \(O(N)\)
• Space complexity: \(O(N)\) (for storing the answer array; the check itself requires only \(O(1)\) additional memory)

Implementation notes

• Since “mountains of the same height are not visible,” the condition should be \(H_i > max_h\), not \(H_i \ge max_h\).

• Since the input size can be large, in Python using sys.stdin.buffer.read() allows for faster reading.

• The output should be the visible mountain numbers on a single line separated by spaces.

  Source Code

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    n = data[0]
    h = data[1:1+n]

    max_h = -1
    ans = []
    for i, hi in enumerate(h, 1):
        if hi > max_h:
            ans.append(i)
            max_h = hi

    sys.stdout.write(" ".join(map(str, ans)))

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.