Overview

This is a problem of finding the minimum number of operations to make all elements of array \(A\) less than or equal to \(0\), where each operation decreases every element in a chosen contiguous interval by \(1\). The answer turns out to be “the sum of increases at positions where the height goes up.”

Analysis

Since each operation “decreases every element in a chosen interval by \(1\),” intuitively we repeatedly select intervals and reduce them. However, simulating this by searching for intervals each time would be far too slow (TLE), as \(A_i\) can be up to \(10^9\), making the number of operations itself extremely large.

The key observation is as follows:

• The snow at position \(i\) needs to be reduced \(A_i\) times.
• However, since reductions can be grouped into intervals, there are portions that can be reduced together between adjacent positions.

This becomes clearer when viewed “layer by layer (by height).” For height \(h\) (\(1 \le h \le \max A\)), positions where \(A_i \ge h\) have a snow layer at height \(h\). For this layer, contiguous portions can be removed in a single operation.

In other words:

• For each height \(h\), “the number of contiguous intervals where \(A_i \ge h\)” is the number of operations needed at that height.
• The total across all heights is the answer.

Counting this directly along the height axis is infeasible, but it can be easily counted by looking along the array direction. The number of newly required operations at position \(i\) is exactly the amount by which the height increased compared to the previous position.

• \(A_1\) is the initial height, so that many operations are needed.
• For \(i \ge 2\), if \(A_i > A_{i-1}\), then “new layers” of size \(A_i - A_{i-1}\) begin, adding to the operation count.
• If \(A_i \le A_{i-1}\), the previous operations already cover it, so no additional operations are needed.

Example: \(A = [2, 1, 3, 3, 1]\) - Initial: \(ans = 2\) - \(1-2=-1\): no addition - \(3-1=2\): add \(+2\) - \(3-3=0\): no addition - \(1-3=-2\): no addition Total: \(2+2=4\)

This can always be done in 4 operations, and it cannot be done in fewer (since the layers at positions where height increases must start being removed from that point), so this is the minimum.

Algorithm

1. Set \(ans = A_1\) (the height of the first position is always needed).
2. Iterate from \(i=2\) to \(N\), computing the difference \(diff = A_i - A_{i-1}\).
3. Only when \(diff > 0\), add \(ans += diff\).
4. Output \(ans\).

This simply means “scan \(A\) from left to right and add only the increases.” Written as a formula: \(ans = A_1 + \sum_{i=2}^{N} \max(0, A_i - A_{i-1})\)

Complexity

• Time complexity: \(O(N)\)
• Space complexity: \(O(N)\) (for storing the input array; \(O(1)\) is possible if processed on the fly without storing)

Implementation Notes

• Since \(N \le 2\times 10^5\), \(O(N)\) is more than sufficient.

• \(A_i\) can be up to \(10^9\) and the answer can be large, but Python’s int supports arbitrary precision, so it is safe as-is.

• Input can be read faster using sys.stdin.buffer.read().

• The essence is “add only positive differences,” so the condition if diff > 0: ans += diff is the core of the solution.

  Source Code

import sys

def main():
    it = iter(sys.stdin.buffer.read().split())
    n = int(next(it))
    a = [int(next(it)) for _ in range(n)]

    ans = a[0]
    for i in range(1, n):
        diff = a[i] - a[i - 1]
        if diff > 0:
            ans += diff

    print(ans)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.