Summary

We find the minimum number of operations to eliminate all “depressions” (i.e., sections that are strictly lower than both their left and right neighbors) using only operations that increase the height of each section.

Analysis

The condition for section \(i\) to be a depression is:

\(H_{i-1} > H_i\) and \(H_i < H_{i+1}\)

To eliminate this depression, we have no choice but to increase the height of section \(i\).
This is because operations cannot decrease heights. Operating on the adjacent sections \(H_{i-1}\) and \(H_{i+1}\) would only make them even higher, which does not help eliminate the depression of section \(i\).

To eliminate the depression of section \(i\), it is sufficient to make its height at least as high as at least one of its left or right neighbors.

In other words, the required height is:

\(\min(H_{i-1}, H_{i+1})\)

Therefore, the number of operations required for a depressed section \(i\) is:

\(\min(H_{i-1}, H_{i+1}) - H_i\)

For example, consider the following heights:

\([5, 2, 4]\)

The middle \(2\) is lower than the left and right elements \(5\) and \(4\), so it is a depression.
To eliminate this depression, we just need to increase its height to at least \(4\), so the required number of operations is:

\(4 - 2 = 2\)

Will new depressions be created?

The problem statement mentions that increasing the height of one section might create a new depression in another section.
However, with this approach, we only increase the height of “originally depressed sections” to the height of the lower of its two neighbors.

Even if we increase the height of section \(i\) to:

\(\min(H_{i-1}, H_{i+1})\)

it only becomes equal in height to one of its neighbors, so it will not make any adjacent section a new depression.

Furthermore, adjacent sections cannot both be depressions at the same time.
This is because if section \(i\) is a depression, then \(H_{i-1} > H_i\) holds, meaning section \(i-1\) cannot satisfy the condition of being strictly lower than its right neighbor.

Therefore, we can consider each depression independently.

Why a naive approach fails

A naive simulation where we repeatedly find depressions and increase their heights by \(1\) could result in a very large number of operations.

Since \(H_i\) can be up to \(10^9\) and \(N\) up to \(10^6\), the total number of operations can be extremely large, leading to TLE (Time Limit Exceeded) if simulated directly.

Instead, we directly calculate “how many times we need to increase the height” for each depression.

Algorithm

Iterate through the sections from left to right, excluding the ends: \(i = 2, 3, \ldots, N-1\).

For each section, if:

\(H_{i-1} > H_i\) and \(H_i < H_{i+1}\)

then the section is a depression.

In this case, the required number of operations is:

\(\min(H_{i-1}, H_{i+1}) - H_i\)

which we add to the total answer.

The final accumulated sum will be the minimum number of operations to eliminate all depressions.

Complexity

• Time Complexity: \(O(N)\)
• Space Complexity: \(O(N)\)

Implementation Details

• Since the sections at both ends are not considered depressions, the range to check is \(1 \leq i \leq N-2\). In 0-indexed terms, this is from i = 1 to i + 1 < N.

• The answer can be as large as \(10^6 \times 10^9 = 10^{15}\), so we must use long long instead of int.

• If \(N \leq 2\), the loop will not execute at all, and the answer will automatically be \(0\).

  Source Code

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;

    vector<long long> H(N);
    for (int i = 0; i < N; i++) cin >> H[i];

    long long ans = 0;

    for (int i = 1; i + 1 < N; i++) {
        if (H[i - 1] > H[i] && H[i] < H[i + 1]) {
            ans += min(H[i - 1], H[i + 1]) - H[i];
        }
    }

    cout << ans << '\n';
    return 0;
}

---

This editorial was generated by gpt-5.5-high.