Overview

Among mountains lined up from front to back, only mountains that are taller than all mountains in front of the current one are visible. The task is to output the numbers of visible mountains in order from front to back.

Analysis

In this problem, “whether a mountain is visible” depends on whether all mountains in front of it have elevations lower than its own. In other words, only mountains taller than the maximum elevation among all preceding mountains become newly visible.

For example, if the mountain elevations are [2, 1, 4, 3, 5]: - The 1st mountain (elevation 2) is the first, so it is visible. - The 2nd (elevation 1) is lower than the 1st, so it is not visible. - The 3rd (elevation 4) is higher than the maximum elevation so far (2), so it is visible. - The 4th (elevation 3) is lower than the maximum elevation (4), so it is not visible. - The 5th (elevation 5) is higher than the maximum elevation (4), so it is visible.

As shown, we can solve this by checking each mountain in order while maintaining the “maximum elevation so far.”

A naive approach of “for each mountain, checking all mountains before it” using a double loop would result in \(O(N^2)\) in the worst case, which cannot finish in time (TLE) since \(N\) can be up to \(2 \times 10^5\). Instead, by keeping track of the “maximum elevation so far” in a variable, we can determine visibility for each mountain in constant time, solving the entire problem in \(O(N)\).

Algorithm

1. Read the number of mountains \(N\) and the elevation list \(H\) from input.
2. Initialize a variable max_height to -1 to record the “maximum elevation so far” (since elevations are positive numbers, the first mountain will always be visible).
3. For each mountain \(i\) (0-indexed), do the following:
   • If h[i] > max_height, the mountain is visible, so add it to the answer and update max_height.
4. Finally, output the numbers of visible mountains separated by spaces (using i + 1 to convert to 1-indexed).

Complexity

• Time complexity: \(O(N)\)
• Space complexity: \(O(1)\) (excluding input)

Implementation Notes

• Numbers must be output in 1-indexed format, so add 1 to the list index (0-indexed).

• Note that the first mountain is always unconditionally visible.

• By initializing max_height to -1, the first mountain is naturally handled as well.

  Source Code

n = int(input())
h = list(map(int, input().split()))

visible_mountains = []
max_height = -1

for i in range(n):
    if h[i] > max_height:
        visible_mountains.append(i + 1)
        max_height = h[i]

print(' '.join(map(str, visible_mountains)))

This editorial was generated by qwen3-coder-480b.