Overview

This is a problem where you need to find the number of mountains visible to the left from each mountain and output the total.

Analysis

In this problem, for each mountain \(i\), we need to find the number of “visible” mountains \(C_i\) among the mountains to its left, and output the sum of all \(C_i\).

What does “visible” mean?

For mountain \(j\) (\(j < i\)) to be visible from mountain \(i\), two conditions must be satisfied:

1. Mountain \(j\) is strictly taller than mountain \(i\): \(H_j > H_i\)
2. All mountains \(k\) between mountain \(j\) and mountain \(i\) (\(j < k < i\)) are shorter than mountain \(j\): \(H_k < H_j\)

The second condition is crucial — we need to determine whether mountain \(j\) is blocked by other mountains.

Naive approach and its problem

The simplest method is, for each mountain \(i\), to iterate through mountains \(j\) from the left and naively check the above conditions. However, this approach has a worst-case time complexity of \(O(N^2)\), which cannot be solved within the time limit (TLE) given the constraint \(N \leq 10^6\).

Idea for an efficient solution

The mountains visible from a given mountain \(i\) are those that are to its left and have no taller mountain between them. A stack is extremely effective for this kind of “maintaining elements that preserve the maximum.”

Specifically, as we process mountains from left to right, mountains shorter than the current mountain will no longer be visible from any future mountain, so we can remove them from the stack. This ensures that only “mountains that may still be visible in the future” remain in the stack.

In other words: - For each mountain \(i\), the number of mountains remaining in the stack equals \(C_i\). - Since each mountain is added to and removed from the stack at most once, the entire process runs in \(O(N)\).

Concrete example

For example, when the input is H = [3, 1, 4, 1, 5]:

• Mountain 1 (height 3): Stack is empty → 0 visible mountains
• Mountain 2 (height 1): Stack=[3] → Mountain with height 3 is visible → 1
• Mountain 3 (height 4): Stack=[3,1] → Both are ≤ 4, so remove them → Stack=[4] → 1 visible
• Mountain 4 (height 1): Stack=[4] → 1 visible
• Mountain 5 (height 5): Stack=[4,1] → Remove both → Stack=[5] → 0 visible

Total = 0 + 1 + 1 + 1 + 0 = 3

Algorithm

1. Process mountains from left to right.
2. For each mountain:
   • Look at the top (back) of the stack; if it is less than or equal to the current mountain’s height, pop it (since it will no longer be visible)
   • The number of mountains remaining in the stack is the number of mountains visible from the current mountain
   • Push the current mountain’s height onto the stack
3. Sum up the number of visible mountains for each mountain and output the result

This stack is maintained in monotonically decreasing order (smallest on top). Therefore, using a deque and operating from the back is efficient.

Complexity

• Time complexity: \(O(N)\)
  Each element is added to the stack at most once and removed at most once, so the total time is linear.
• Space complexity: \(O(N)\)
  The stack stores at most \(N\) elements.

Implementation notes

• Using a deque for stack operations is efficient (especially for back operations)

• For each mountain, “number of visible mountains = length of the stack”

• Note that mountains of the same height are not visible (\(H_j > H_i\) is required)

  Source Code

import sys
from collections import deque

def main():
    input = sys.stdin.read
    data = input().split()
    N = int(data[0])
    H = list(map(int, data[1:]))

    # 左から右へ処理するためのスタック
    stack = deque()
    total = 0

    for i in range(N):
        h = H[i]
        # スタックの上から見て、現在の高さ以上なら取り除く（見える可能性がない）
        while stack and stack[-1] <= h:
            stack.pop()
        # 残っている山の数が、現在の山から見える山の数
        total += len(stack)
        # 現在の山の高さをスタックに追加
        stack.append(h)

    print(total)

if __name__ == "__main__":
    main()

---

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