Overview

This problem asks us to reduce the snow amounts in \(N\) given sections all to \(0\) using the minimum number of “subtraction operations on intervals.” This is a classic problem in competitive programming that can be solved efficiently by focusing on the differences between adjacent elements.

Approach

First, let’s think through a concrete example. Consider the snow amounts [1, 3, 2].

1. Section 1 (amount: 1): The snow has increased by \(1\) compared to the previous section (treated as \(0\)). To remove this \(1\) centimeter, at least \(1\) snow removal operation is needed.
2. Section 2 (amount: 3): There are \(2\) more centimeters of snow than the previous section (amount: 1). Even if we extend the snow removal from the previous section, it only reduces \(1\) centimeter, so we need to start \(2\) additional new snow removal operations for this section.
3. Section 3 (amount: 2): There is less snow than the previous section (amount: 3). The snow in this section can be handled as part of the snow removal operations already being performed on section 2, so there is no need to start any new operations.

The key insight is that “we must start new snow removal operations exactly for the amount by which the snow increases compared to the previous section.”

Conversely, when the snow decreases compared to the previous section, we simply end some of the ongoing snow removal operations before reaching this section, so no additional operations are needed.

Algorithm

This problem can be solved with the following steps:

1. Initialize a variable ans to hold the answer as \(0\), and a variable prev_snow to hold the snow amount of the previous section as \(0\).
2. Iterate through each section’s snow amount \(A_i\) from left to right.
3. If the current snow amount \(A_i\) is greater than prev_snow, add the difference (\(A_i - prev\_snow\)) to ans.
4. Update prev_snow to the current \(A_i\).
5. After processing all sections, ans is the minimum number of operations.

This approach is very fast since it only requires checking each element once.

Complexity

• Time Complexity: \(O(N)\)
  • Since we scan through \(N\) elements once, the computation finishes in time proportional to the input size.
• Space Complexity: \(O(N)\)
  • \(O(N)\) memory is used when storing the input values as a list.

Implementation Notes

• Handling large input: Since \(N\) can be as large as \(2 \times 10^5\), in Python you can reduce execution time by reading all input at once using sys.stdin.read().split() or similar methods.

• Difference calculation: By treating the first element \(A_1\) as “increasing from \(0\) to \(A_1\),” we can handle it uniformly within the loop.

• Magnitude of values: Since the snow amount \(A_i\) can reach up to \(10^9\), the total sum may exceed the range of \(32\)-bit integers. In Python, this is not an issue since integers are automatically handled as arbitrary-precision, but in other languages (such as C++) you need to use types like long long.

  Source Code

import sys

def main():
    # Read all input data at once and split into tokens
    # Using sys.stdin.read().split() is efficient for the given constraints
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # The first token is N, the number of sections
    n = int(input_data[0])
    
    # The following tokens are the snow amounts A_1, A_2, ..., A_N
    # The problem asks for the minimum number of range-decrement operations
    # to make all snow amounts 0 or less. In the context of "snow shoveling"
    # problems, this typically implies that you can only shovel sections
    # where snow actually exists (A_i > 0). This is a classic problem
    # equivalent to AtCoder Beginner Contest 116 C - Grand Garden.
    # The minimum number of operations is the sum of positive differences
    # between adjacent sections: sum(max(0, A_i - A_{i-1})) where A_0 = 0.
    
    ans = 0
    prev_snow = 0
    
    # Iterate through each section's snow amount
    # input_data[1] is A_1, input_data[2] is A_2, ..., input_data[n] is A_n
    for i in range(1, n + 1):
        current_snow = int(input_data[i])
        # If the current section has more snow than the previous one,
        # we must start at least (current_snow - prev_snow) new operations
        # that cover this section but did not cover the previous one.
        if current_snow > prev_snow:
            ans += (current_snow - prev_snow)
        prev_snow = current_snow
    
    # Output the total minimum number of operations
    print(ans)

if __name__ == '__main__':
    main()

This editorial was generated by gemini-3-flash-thinking.