Overview

There are \(N\) mountains lined up in a row, and the problem asks for the total number of mountains that are “visible” looking to the left from each mountain. By using a monotonic stack to find “where the next mountain with height greater than or equal to the current one is located to the right,” we can solve this efficiently.

Analysis

Changing the way we count pairs

Since we want to find the total of \(C_i\), the number of mountains \(j\) visible from each mountain \(i\), we can reframe this as counting the total number of “visible” pairs \((j, i)\) where \(j < i\).

Organizing the conditions for a pair \((j, i)\) to be “visible”: - \(H_j > H_i\) (mountain \(j\) is strictly taller than mountain \(i\)) - For all \(k\) such that \(j < k < i\), \(H_k < H_j\) (all mountains in between are lower than \(H_j\))

Combining these two conditions, this is equivalent to \(H_j > \max(H_{j+1}, H_{j+2}, \ldots, H_i)\). In other words, all mountains from the right neighbor of \(j\) through \(i\) must be strictly lower than \(H_j\).

Thinking from the perspective of mountain \(j\)

For a fixed mountain \(j\), what is the range of valid \(i\)?

Looking rightward from \(i = j+1\), pairs are valid as long as \(H_{j+1}, H_{j+2}, \ldots\) are all less than \(H_j\). However, once the first mountain \(k\) with \(H_k \geq H_j\) appears, for \(i = k\) and beyond, \(\max(H_{j+1}, \ldots, H_i) \geq H_j\) holds, and the condition is no longer satisfied.

In other words, if we define \(\text{next\_ge}(j)\) as “the smallest index \(k > j\) such that \(H_k \geq H_j\),” then the number of pairs that can be formed from mountain \(j\) is:

\[\text{next\_ge}(j) - j - 1\]

Concrete example: For \(H = [5, 3, 2, 4, 1]\): - \(j=0\) (\(H=5\)): No mountain with height \(\geq 5\) to the right → \(\text{next\_ge}(0) = 5\), pairs \(= 5 - 0 - 1 = 4\) - \(j=1\) (\(H=3\)): \(H_3 = 4 \geq 3\) → \(\text{next\_ge}(1) = 3\), pairs \(= 3 - 1 - 1 = 1\) - \(j=2\) (\(H=2\)): \(H_3 = 4 \geq 2\) → \(\text{next\_ge}(2) = 3\), pairs \(= 3 - 2 - 1 = 0\) - \(j=3\) (\(H=4\)): No mountain with height \(\geq 4\) to the right → \(\text{next\_ge}(3) = 5\), pairs \(= 5 - 3 - 1 = 1\) - \(j=4\) (\(H=1\)): No mountain to the right → \(\text{next\_ge}(4) = 5\), pairs \(= 5 - 4 - 1 = 0\)

Total \(= 4 + 1 + 0 + 1 + 0 = 6\)

The problem with the naive approach

If we scan rightward for each \(j\) to find \(\text{next\_ge}(j)\), the worst case is \(O(N^2)\), which will TLE for \(N = 10^6\).

Algorithm

We use a monotonic stack to compute \(\text{next\_ge}(j)\) for all \(j\) in \(O(N)\).

1. Prepare a stack (storing indices).
2. Scan in order \(k = 0, 1, \ldots, N-1\).
3. For each \(k\), while the mountain \(j\) at the top of the stack satisfies \(H_j \leq H_k\), pop \(j\) and record \(\text{next\_ge}(j) = k\).
4. Push \(k\) onto the stack.
5. After the scan, mountains remaining in the stack have no mountain to their right with height greater than or equal to theirs, so \(\text{next\_ge}(j) = N\) (the initial value).

Finally, compute and output \(\displaystyle\sum_{j=0}^{N-1} (\text{next\_ge}(j) - j - 1)\).

Stack property: The heights of mountains in the stack are always maintained in strictly decreasing order. If \(H_k\) is greater than or equal to the top of the stack, the top is popped, creating a structure where smaller elements are “eliminated” by larger ones. Each element is pushed and popped exactly once, so the overall complexity is \(O(N)\).

Complexity

• Time complexity: \(O(N)\) (each element enters and leaves the stack exactly once)
• Space complexity: \(O(N)\) (for the array and the stack)

Implementation Notes

• Initialize \(\text{next\_ge}\) to \(N\): Elements remaining in the stack have no qualifying mountain even beyond the right end, so \(\text{next\_ge}(j) = N\) is the correct value.

• The pop condition is \(H_j \leq H_k\) (including equality): Since we are looking for the “next mountain with height greater than or equal to” the current one, we also pop when the heights are equal.

• Fast input: Since \(N\) can be up to \(10^6\), we use sys.stdin.buffer.read() to read all input at once for faster I/O.

  Source Code

import sys

def solve():
    input_data = sys.stdin.buffer.read().split()
    N = int(input_data[0])
    H = [int(input_data[i+1]) for i in range(N)]
    
    # For each mountain i, we need to count how many mountains j < i are "visible" from i.
    # Mountain j is visible from i if:
    #   1. H[j] > H[i]
    #   2. For all k with j < k < i, H[k] < H[j]
    
    # Condition 2 means: H[j] is strictly greater than all mountains between j and i.
    # This means H[j] must be strictly greater than the maximum of H[j+1..i-1].
    
    # Key insight: Consider maintaining a stack of "visible candidates" from left to right.
    # The stack maintains mountains in decreasing order of height (monotone stack).
    
    # For each mountain i, the mountains that are visible from i are exactly those
    # mountains j in the stack (when processing i) such that H[j] > H[i].
    
    # Let's think differently. We want sum over all i of C_i.
    # Equivalently, we count the number of pairs (j, i) with j < i such that:
    #   (a) H[j] > H[i]
    #   (b) max(H[j+1..i-1]) < H[j]  (vacuously true if j = i-1)
    
    # Condition (b) means H[j] > H[k] for all j < k < i.
    # Combined: H[j] > max(H[i], max of H[j+1..i-1]) = max(H[j+1..i])... wait no.
    # H[j] > H[k] for all j < k < i, AND H[j] > H[i].
    # So H[j] > max(H[j+1], ..., H[i]).
    
    # So we need to count pairs (j, i) with j < i where H[j] > max(H[j+1..i]).
    
    # For a fixed j, the mountains i > j where H[j] > max(H[j+1..i]) are:
    # i = j+1, j+2, ... up to the first index where H[k] >= H[j] for some k in [j+1..i].
    # Actually, we need max(H[j+1..i]) < H[j].
    # Starting from i = j+1: max = H[j+1]. Valid if H[j+1] < H[j].
    # i = j+2: max = max(H[j+1], H[j+2]). Valid if both < H[j].
    # Continue until we hit some index where H >= H[j].
    
    # So for each j, the count is the number of consecutive elements after j that are all
    # strictly less than H[j], i.e., the distance to the first element >= H[j] to the right.
    
    # This is a classic "next greater or equal element" problem solvable with a monotone stack.
    
    # For each j, let next_ge[j] be the smallest index k > j such that H[k] >= H[j].
    # If no such k exists, next_ge[j] = N.
    # Then the number of valid i for this j is: next_ge[j] - j - 1.
    # Wait: valid i range is j+1 to next_ge[j]-1 (inclusive), 
    # because at next_ge[j], max(H[j+1..next_ge[j]]) >= H[j].
    # Count = next_ge[j] - 1 - (j+1) + 1 = next_ge[j] - j - 1.
    
    # Total answer = sum over j of (next_ge[j] - j - 1).
    
    # Find next_ge using monotone stack (from right to left, or left to right).
    
    next_ge = [N] * N
    stack = []  # stack of indices, maintaining increasing order of index, decreasing won't work simply
    
    # Standard approach: iterate from right to left
    # Actually, let's use left-to-right with a stack storing indices in decreasing H order.
    
    # Left to right: maintain stack. For each new element H[k], pop all stack elements with H < H[k]... 
    # we need next >= , so pop while stack top has H[stack_top] <= H[k]? No.
    # We want next_ge[j] = first k > j with H[k] >= H[j].
    # Use a stack: iterate k from left to right. For each k, pop all j from stack where H[j] <= H[k],
    # and set next_ge[j] = k. Then push k.
    
    stack = []
    for k in range(N):
        while stack and H[stack[-1]] <= H[k]:
            j = stack.pop()
            next_ge[j] = k
        stack.append(k)
    
    ans = 0
    for j in range(N):
        ans += next_ge[j] - j - 1
    
    print(ans)

solve()

---

This editorial was generated by claude4.6opus-thinking.