Overview

There are \(N\) mountains lined up, and a mountain is “visible” if its elevation is higher than all the mountains in front of it. The problem asks us to extract the numbers of all mountains that satisfy this condition.

Analysis

To determine whether a mountain \(i\) is visible, following the definition directly requires checking “the elevations of all mountains from the 1st to the \((i-1)\)-th.”

However, checking all mountains every time results in the following computational cost: - Checking the 1st mountain: 0 comparisons - Checking the 2nd mountain: 1 comparison - Checking the 3rd mountain: 2 comparisons - … - Checking the \(N\)-th mountain: \(N-1\) comparisons

The total number of comparisons is roughly \(\frac{N^2}{2}\), which for the given constraint \(N = 2 \times 10^5\) requires about \(2 \times 10^{10}\) operations. Under the typical time limit of competitive programming contests (2 seconds), approximately \(10^8\) operations is the limit, so this “naive approach” would result in a Time Limit Exceeded (TLE).

Here, we notice that if we only know “the highest elevation among the mountains in front,” there is no need to compare against all mountains. The condition for mountain \(i\) to be visible can be rephrased as: - \(H_i > (\text{maximum elevation among mountains from the 1st to the } (i-1)\text{-th})\)

By examining the mountains from front to back and continuously updating the maximum elevation seen so far, we can determine the visibility of each mountain with just a single comparison.

Algorithm

Prepare a variable (current_max_height) to hold “the maximum elevation among mountains seen so far.”

1. Initialize current_max_height to \(0\).
2. For \(i = 1\) to \(N\), perform the following in order:
   • If the current mountain’s elevation \(H_i\) is higher than current_max_height:
     • That mountain is “visible,” so record the number \(i\).
     • Update current_max_height to \(H_i\).
   • Otherwise (if \(H_i\) is less than or equal to current_max_height):
     • That mountain is not visible, so do nothing.
3. Output the recorded numbers in order.

Complexity

• Time complexity: \(O(N)\)
  • For \(N\) mountains, we only check each one once from front to back, so the number of elevation comparisons is \(N\). This runs sufficiently fast even for \(N = 2 \times 10^5\).
• Space complexity: \(O(N)\)
  • \(O(N)\) memory is used for the list of input elevations and the list storing the mountain numbers in the answer.

Implementation Notes

• 1-based indexing: Since the problem numbers mountains starting from 1, be careful that the 0th element in the program corresponds to “mountain number 1” when producing output.

• Updating the maximum: By updating current_max_height, we can always compare against “the tallest mountain in front of the current one.”

• Fast I/O: In Python, using sys.stdin.read().split() allows reading large inputs quickly. Also, print(*list) can concisely output the contents of a list separated by spaces.

  Source Code

import sys

def solve():
    # 入力を標準入力からすべて読み込む
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    n = int(input_data[0])
    h = list(map(int, input_data[1:]))
    
    visible_mountains = []
    current_max_height = 0
    
    for i in range(n):
        # 現在の山の標高がこれまでの最大標高よりも高い場合、その山は見える
        if h[i] > current_max_height:
            visible_mountains.append(i + 1)
            current_max_height = h[i]
            
    # 見える山の番号をスペース区切りで出力
    print(*(visible_mountains))

if __name__ == '__main__':
    solve()

This editorial was generated by gemini-3-flash-preview.