Summary

We want to find the minimum number of operations to make the sequence \(H\) mountain-shaped, where each operation consists of choosing an interval and decreasing its height by \(1\).

As a conclusion, the answer is

\[ H_1 + \sum_{i=2}^{N} \max(0, H_i - H_{i-1}) - \max_i H_i \]

Analysis

First, let’s consider the question: “How many operations are required to make all elements of a height sequence \(0\)?”

Let the height sequence be \(X_1, X_2, \ldots, X_N\).
The minimum number of operations to make this entire sequence \(0\) is

\[ X_1 + \sum_{i=2}^{N} \max(0, X_i - X_{i-1}) \]

The reason becomes clear when we look at it from left to right:

• Since the \(1\)-st element has \(X_1\) “layers of height”, at least \(X_1\) interval operations are required.
• When moving from the \((i-1)\)-th to the \(i\)-th element, if \(X_i > X_{i-1}\), then \(X_i - X_{i-1}\) new layers begin.
• Accordingly, that many new operations are required.
• Conversely, if \(X_i \le X_{i-1}\), no new layers begin, so no additional operations are needed.

For example, if \(X = [2, 1, 3, 2]\):

\[ 2 + \max(0,1-2) + \max(0,3-1) + \max(0,2-3) = 2 + 0 + 2 + 0 = 4 \]

Thus, we can make all elements \(0\) in \(4\) operations.

---

Next, consider the case where the final remaining sequence is mountain-shaped.

The minimum number of operations to make a mountain-shaped sequence \(A\) entirely \(0\) is exactly its maximum value.

This is because, in a mountain shape, the height is monotonically non-decreasing up to the peak, and monotonically non-increasing after the peak.
Therefore, the number of “newly starting layers” when viewed from the left is only the height of the peak, which is \(\max A_i\).

---

Here, let the minimum number of operations to make the original sequence \(H\) entirely \(0\) be

\[ F(H) = H_1 + \sum_{i=2}^{N} \max(0, H_i - H_{i-1}) \]

Suppose we can transform \(H\) into a mountain-shaped sequence \(A\) using \(m\) operations.
After that, we need an additional \(\max A_i\) operations to make \(A\) entirely \(0\).

Therefore,

\[ m + \max A_i \ge F(H) \]

holds.

Also, since we cannot increase the height in any operation,

\[ \max A_i \le \max H_i \]

holds.

Thus,

\[ m \ge F(H) - \max H_i \]

holds.

In other words, any method requires at least

\[ F(H) - \max H_i \]

operations.

---

On the other hand, we can actually make the sequence mountain-shaped with this number of operations.

Let’s view the original sequence as “layers” of different heights.
Let \(p\) be the position where the maximum value is achieved.

For each height level, consider leaving only the connected component containing position \(p\) and removing all other layers.

Then, the remaining height sequence satisfies:

• to the left of \(p\), the height does not decrease as we get closer to \(p\)
• to the right of \(p\), the height does not increase as we move away from \(p\)

which guarantees that it is mountain-shaped.

The number of remaining layers in this case is exactly \(\max H_i\).
Since we originally needed \(F(H)\) operations to remove everything, the number of operations to remove the rest is

\[ F(H) - \max H_i \]

This matches the lower bound, so this is indeed the minimum number of operations.

Algorithm

The value to find is

\[ H_1 + \sum_{i=2}^{N} \max(0, H_i - H_{i-1}) - \max_i H_i \]

Therefore, we can compute this by scanning from left to right once as follows:

1. Record the initial height \(H_1\).
2. Compare adjacent elements, and if \(H_i > H_{i-1}\), add \(H_i - H_{i-1}\) to the sum of increments.
3. Update the overall maximum value \(\max H_i\).
4. Finally, output:

\[ \text{Answer} = H_1 + \text{sum of increments} - \max H_i \]

For example, if \(H = [2, 1, 3, 2]\):

\[ H_1 = 2 \]

The only increasing part is \(1 \to 3\), so

\[ \sum \max(0, H_i - H_{i-1}) = 2 \]

Also,

\[ \max H_i = 3 \]

Thus, the answer is

\[ 2 + 2 - 3 = 1 \]

Indeed, if we decrease only the \(1\)-st element by \(1\), we get

\[ [2,1,3,2] \to [1,1,3,2] \]

which is mountain-shaped.

Complexity

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

Implementation Points

Since \(H_i\) can be up to \(10^9\) and \(N\) up to \(10^6\), the sum of increments may not fit in a 32-bit integer.

Therefore, the answer and intermediate sums must be stored in a 64-bit integer type (such as long long in C++).

Also, if \(N=1\), the sequence is always mountain-shaped from the start.
In this case,

\[ H_1 - \max H_i = 0 \]

so the answer becomes \(0\) without any special case handling.

Source Code

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

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

    int N;
    cin >> N;

    long long h, prev;
    cin >> h;

    long long first = h;
    long long maxH = h;
    long long totalRise = 0;
    prev = h;

    for (int i = 1; i < N; i++) {
        cin >> h;
        if (h > prev) totalRise += h - prev;
        maxH = max(maxH, h);
        prev = h;
    }

    cout << totalRise + first - maxH << '\n';
    return 0;
}

---

This editorial was generated by gpt-5.5-high.