Overview

Each person \(i\)’s ball flies to “the first person to the right who is taller,” so we first find that person (the next greater element), then efficiently compute the range minimum \(\min(H_i,\dots,H_j)\) and sum up the results.

Analysis

Key Observations

• The person who catches person \(i\)’s ball is the smallest \(j\) such that \(j>i\) and \(H_j>H_i\) (the Next Greater Element to the right).
• The cost when the ball is caught is the minimum value in the range \([i, j]\), i.e., \(\min(H_i,\dots,H_j)\) (inclusive of both endpoints).

Therefore, for each \(i\): 1. Find the catcher \(j\) (if none exists, the cost is \(0\)) 2. Add the range minimum for that interval

This is the problem we need to solve.

Why a Naive Solution Is Too Slow

• For each \(i\), scanning to the right to find “the first taller person”: worst case \(O(N)\)
• For the found \(j\), scanning again to find the range minimum: worst case \(O(N)\)

Doing this for all people results in worst case \(O(N^2)\), which is too slow for \(N \le 2\times 10^5\).

Solution Strategy

• The “first taller person to the right (NGE)” can be found in \(O(N)\) overall using a monotonic stack.
• The “range minimum” can be answered in \(O(\log N)\) using a segment tree (RMQ).

This gives an overall time complexity of \(O(N \log N)\).

Algorithm

1. Finding the Next Greater Element (the catcher) with a Monotonic Stack

We scan from left to right, maintaining a stack of “people who haven’t yet found a taller person to their right,” keeping heights in monotonically decreasing order.

Let \(h\) be the height of the current person: - If the person \(k\) at the top of the stack satisfies \(H_k < h\), then the “first taller person to the right” for \(k\) is exactly the current person, so we set nge[k] = current index and pop \(k\) from the stack. - We repeat this process, and finally push the current person onto the stack.

This gives us nge[i] for each \(i\) (-1 if no such person exists). Note: Since the condition is “strictly taller,” we use \(<\) for comparison (people of the same height do not satisfy the catching condition).

2. Finding the Range Minimum \(\min(H_i,\dots,H_j)\) with a Segment Tree

Once nge[i]=j is determined, the cost is the minimum of the range \([i, j]\). To compute this efficiently, we build a segment tree that returns the range minimum over array \(H\).

• Leaves store the values of \(H\), and internal nodes hold the minimum of their left and right children.
• For each \(i\) where j != -1, we query the segment tree for the minimum of \([i, j]\) in \(O(\log N)\) and add it to the total.
• When j == -1, the cost is \(0\), so we skip it.

(Example) For \(H = [2, 1, 3]\): - \(i=0(2)\): the next taller person is \(j=2(3)\), range minimum is \(\min(2,1,3)=1\) - \(i=1(1)\): the next taller person is \(j=2(3)\), range minimum is \(\min(1,3)=1\) - \(i=2(3)\): no one to the right, so \(0\) The total is \(2\).

Complexity

• Time complexity:
  • NGE computation (monotonic stack): \(O(N)\)
  • RMQ for each \(i\) (segment tree): \(N\) queries × \(O(\log N)\) = \(O(N\log N)\) Total: \(O(N\log N)\)
• Space complexity:
  • nge, stack, and segment tree: \(O(N)\)

Implementation Notes

• Since the catching condition is “strictly taller,” the monotonic stack uses H[stack[-1]] < h (not <=).

• Note that the cost minimum covers the range \([i, j]\) inclusive of both endpoints.

• Setting the segment tree size to the smallest \(2^k \ge N\) simplifies implementation (in the code: size = 1 << (N - 1).bit_length()).

• In Python, due to large input data, sys.stdin.buffer.read() is used for fast input, and the segment tree array uses array('q') for speed optimization.

  Source Code

import sys
from array import array

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

    nge = [-1] * N
    stack = []
    for idx, h in enumerate(H):
        while stack and H[stack[-1]] < h:
            nge[stack.pop()] = idx
        stack.append(idx)

    size = 1 << (N - 1).bit_length()
    base = size
    INF = 10**18

    seg = array('q', [INF]) * (2 * size)
    seg[base:base + N] = array('q', H)

    for i in range(base - 1, 0, -1):
        a = seg[2 * i]
        b = seg[2 * i + 1]
        seg[i] = a if a < b else b

    total = 0
    for i, j in enumerate(nge):
        if j == -1:
            continue
        l = i + base
        r = j + base
        res = INF
        while l <= r:
            if l & 1:
                v = seg[l]
                if v < res:
                    res = v
                l += 1
            if not (r & 1):
                v = seg[r]
                if v < res:
                    res = v
                r -= 1
            l >>= 1
            r >>= 1
        total += res

    sys.stdout.write(str(total))

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.