Overview

For each mountain \(i\), we compute the number of “mountains visible to the left” \(C_i\), then efficiently calculate the total sum \(\sum_{i=1}^{N} C_i\). The key insight is that “visible mountains” are only the unobstructed taller mountains to the left, which can be managed collectively using a monotonic stack.

Analysis

When looking left from mountain \(i\), mountain \(j\,(j<i)\) is visible if and only if:

• (1) \(H_j > H_i\) (strictly taller than \(i\))
• (2) For all \(k\) with \(j<k<i\), \(H_k < H_j\) (no mountain of height \(H_j\) or greater lies in between)

Condition (2) equivalently means “mountain \(j\) is the tallest in the interval \((j,i)\) (not even allowing equal height).”

Why the Naive Approach Fails

For each \(i\), we could scan leftward while updating the “maximum seen so far” and counting, but in the worst case: - \(i=1\): 0 comparisons - \(i=2\): 1 comparison - … - \(i=N\): \(N-1\) comparisons

This totals \(O(N^2)\) comparisons. For \(N \le 10^6\), this is far too slow.

Key Observation

When processing mountains from left to right, we only need to keep “mountains that could potentially be visible from future mountains.”

• Let the height of a new mountain be \(h\).
• If mountains with height \(\le h\) remain on the left, they cannot satisfy condition (1) \(H_j > H_i\) (at least they are not visible from this mountain of height \(h\)).
• Furthermore, even when viewed from mountains further to the right in the future, this mountain of height \(h\) stands in between, so mountains with height \(\le h\) become obstructed and invisible (they are eliminated by condition 2).

Therefore, all heights \(\le h\) at the end of the stack can be discarded at once.

Algorithm

We use a strictly decreasing monotonic stack. Processing mountains from left to right, we push only heights onto the stack such that they remain in strictly decreasing order.

For each mountain height \(h=H_i\) processed in order:

1. While the top of the stack is \(\le h\), pop it
   
   • while stack and stack[-1] <= h: stack.pop()
   • Using <= here is crucial (equal heights are not visible by condition 1, and they also obstruct by condition 2, so keeping equal heights would be incorrect).
2. After popping, all remaining elements in the stack are \(> h\), and the stack is monotonically decreasing
   
   • At this point, every mountain remaining in the stack is visible from the current mountain.
   • Reason: If a mountain of equal or greater height existed to the right of a stack element (i.e., between it and the current mountain), it would have already been popped and removed, so there is nothing to obstruct the view.
3. Therefore, add \(C_i = \text{len(stack)}\) to the answer
   
   • ans += len(stack)
4. Push the current mountain height \(h\) onto the stack
   
   • stack.append(h)

Simple Example

Processing \(H=[5,3,4,2]\):

• \(5\): stack=[] → ans+=0, push 5 → [5]
• \(3\): no pops → ans+=1 (5 is visible), push 3 → [5,3]
• \(4\): 3 is <=4 so pop → [5] → ans+=1 (5 is visible), push 4 → [5,4]
• \(2\): no pops → ans+=2 (5 and 4 are visible), push 2 → [5,4,2]

Total sum is \(0+1+1+2=4\).

Complexity

• Time complexity: \(O(N)\)
  Each element is pushed onto the stack once and popped at most once, so the overall work is linear.
• Space complexity: \(O(N)\)
  In the worst case (a monotonically decreasing sequence), \(N\) elements are on the stack.

Implementation Notes

• Pop with <=:
  Equal heights are “not visible” and “obstruct,” so the stack must be maintained as strictly decreasing.

• With \(N=10^6\), I/O can easily become a bottleneck. The provided code uses sys.stdin.buffer.read() to read all input at once and parse integers efficiently.

• ans can be as large as approximately \(O(N^2)\) (for a monotonically decreasing sequence, \(\sum_{i=1}^N (i-1)\)), which could exceed 64 bits. However, Python’s integers have arbitrary precision, so this is not an issue.

  Source Code

import sys


def ints():
    data = sys.stdin.buffer.read()
    n = len(data)
    i = 0
    while i < n:
        while i < n and data[i] <= 32:
            i += 1
        if i >= n:
            break
        x = 0
        while i < n and data[i] > 32:
            x = x * 10 + (data[i] - 48)
            i += 1
        yield x


it = ints()
N = next(it)

stack = []
ans = 0

for _ in range(N):
    h = next(it)
    while stack and stack[-1] <= h:
        stack.pop()
    ans += len(stack)
    stack.append(h)

sys.stdout.write(str(ans))

---

This editorial was generated by gpt-5.2-high.