Overview

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

The key observation is that if we fix the peak of the mountain at index \(k\), the cost on the left side is determined only by the “decreasing adjacent differences”, and the cost on the right side is determined only by the “increasing adjacent differences”.

Analysis

Suppose we fix the peak of the mountain at index \(k\).

The conditions required are as follows:

• The left side \(1,2,\ldots,k\) is monotonically non-decreasing.
• The right side \(k,k+1,\ldots,N\) is monotonically non-increasing.

That is, we must satisfy

\[ H'_i \le H'_{i+1} \]

on the left side, and

\[ H'_i \ge H'_{i+1} \]

on the right side.

Required Number of Operations on the Left Side

For adjacent elements \(i, i+1\) on the left side, if the original heights satisfy

\[ H_i > H_{i+1} \]

this violates the non-decreasing condition on the left side.

Letting the difference be

\[ d = H_i - H_{i+1} \]

to eventually satisfy \(H'_i \le H'_{i+1}\), we must decrease the height of element \(i\) at least \(d\) more times than element \(i+1\).

To decrease element \(i\) but not element \(i+1\) using interval operations, the right end of the chosen interval must be exactly \(i\).

Therefore, at least \(d\) operations are required to resolve this adjacent difference.

Thus, the required number of operations on the left side is

\[ \sum_{i=1}^{k-1} \max(0, H_i - H_{i+1}) \]

Required Number of Operations on the Right Side

Similarly, the right side must be monotonically non-increasing.

If

\[ H_i < H_{i+1} \]

this violates the condition on the right side.

Letting the difference be

\[ d = H_{i+1} - H_i \]

we must decrease element \(i+1\) at least \(d\) more times than element \(i\).

This can be achieved by operations where the left end of the chosen interval is exactly \(i+1\).

Therefore, the required number of operations on the right side is

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

Answer when the peak \(k\) is fixed

From the above, the minimum number of operations when the peak is fixed at \(k\) is

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

All we need to do is minimize this value over all possible \(k\).

A naive approach that scans the left and right sides for each \(k\) would take \(O(N^2)\) time, which is too slow for \(N \le 10^6\).

Therefore, we will incrementally update the left and right costs.

Algorithm

First, consider the case where the peak is \(k=1\).

In this case, the left side is empty, so we only need the cost to make the right side monotonically non-increasing.

That is, we first calculate

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

Let this be suffix_up.

Also, let the cost on the left side be prefix_down, initialized to \(0\).

Next, we move the peak from left to right.

When we move the peak from \(k\) to \(k+1\), the boundary \((k, k+1)\) shifts from the “right side” to the “left side”.

Therefore, we perform the following updates:

• If \(H_k > H_{k+1}\), add \(H_k - H_{k+1}\) to the left-side cost.
• If \(H_k < H_{k+1}\), subtract \(H_{k+1} - H_k\) from the right-side cost.

At each position, we calculate

\[ \text{prefix\_down} + \text{suffix\_up} \]

and the minimum value among these is the answer.

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

• \(k=1\): The increasing difference on the right side is \(1 \to 4\), so the cost is \(3\).
• \(k=2\): The decreasing difference on the left side \(3 \to 1\) is \(2\), and the increasing difference on the right side \(1 \to 4\) is \(3\), totaling \(5\).
• \(k=3\): The decreasing difference on the left side \(3 \to 1\) is \(2\), and the right-side cost is \(0\), totaling \(2\).
• \(k=4\): The decreasing differences on the left side \(3 \to 1\) and \(4 \to 2\) total \(4\).

Thus, the answer is \(2\).

Complexity

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

It takes \(O(N)\) space to store the input array \(H\). Since we only use a constant number of additional variables, the auxiliary space complexity is \(O(1)\).

Key Implementation Details

• If \(N=1\), the array is already mountain-shaped, so the answer is \(0\).

• Since the answer can be up to around \(10^{15}\), you need to use a 64-bit integer type like long long in languages like C++.

• In Python, you do not need to worry about integer overflow.

• In the implementation, 0-indexing is used, so the boundary \(i\) represents the boundary between H[i] and H[i+1].

  Source Code

import sys

def main():
    input = sys.stdin.buffer.readline
    N = int(input())
    H = list(map(int, input().split()))

    if N == 1:
        print(0)
        return

    suffix_up = 0
    for i in range(N - 1):
        a = H[i]
        b = H[i + 1]
        if b > a:
            suffix_up += b - a

    prefix_down = 0
    ans = suffix_up

    for i in range(N - 1):
        a = H[i]
        b = H[i + 1]
        if a > b:
            prefix_down += a - b
        elif b > a:
            suffix_up -= b - a

        v = prefix_down + suffix_up
        if v < ans:
            ans = v

    print(ans)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.5-high.