Overview

This problem asks for the minimum number of operations to transform a given sequence \(H\) into a mountain-shaped sequence \(H'\) with a specific element \(H'_k\) as its peak, by repeatedly applying the operation “decrement an interval by \(1\)”.

Since the constraint \(N \le 10^6\) is large, we can take an \(O(N)\) approach by trying all possible peak positions \(k\) (\(1 \le k \le N\)) and calculating the minimum number of operations for each \(k\) in \(O(1)\) time.

---

Analysis

1. Fixing the Peak \(k\)

The final sequence \(H'\) being “mountain-shaped” means there exists some peak \(k\) such that the left side (\(1 \le i \le k\)) is monotonically non-decreasing, and the right side (\(k \le i \le N\)) is monotonically non-increasing. To unify the boundary conditions, we prepend and append \(H_0 = 0\) and \(H_{N+1} = 0\) to the sequence.

When the peak \(k\) is fixed, the conditions to be satisfied are as follows: - Left side: \(0 = H'_0 \le H'_1 \le H'_2 \le \cdots \le H'_k\) - Right side: \(H'_k \ge H'_{k+1} \ge \cdots \ge H'_N \ge H'_{N+1} = 0\)

2. Number of Operations to Make the Left Side Monotonically Non-Decreasing

To make the left side \(1 \dots k\) monotonically non-decreasing, we need to resolve any adjacent elements where a decrease occurs (\(H_{i-1} > H_i\)). To resolve this using interval decrement operations, we must decrement the left side of the decreasing step.

Once we decide the final height of the peak \(k\) to be \(H'_k\), the minimum number of operations \(C_L(H'_k)\) to make the left side monotonically non-decreasing can be expressed as: $\(C_L(H'_k) = L_k - H'_k\)\( Here, \)L_k\( is the sum of the "increases" (\)Hi - H{i-1} > 0\() in the original sequence from index \)0\( to \)k$.

Concrete Example

Let \(H = [0, 3, 1, 4]\) and \(k=3\) (\(H_3 = 4\)). - Sum of increases \(L_3 = (3 - 0) + (4 - 1) = 6\) - Sum of decreases \(sumB[3] = (3 - 1) = 2\)

To make the left side monotonically non-decreasing, we need to resolve the decreasing step from \(3\) to \(1\) (a decrease of 2). This requires decrementing the \(3\) on the left side down to \(1\). This operation transforms the sequence into \([1, 1, 4]\) with \(2\) operations. At this point, the peak height remains \(4\). If we further want to lower the peak height to \(H'_3 = 2\), we perform \(2\) additional operations to obtain \([1, 1, 2]\). The total number of operations becomes \(2 + 2 = 4\). This matches the formula \(C_L(H'_3) = L_3 - H'_3 = 6 - 2 = 4\).

3. Number of Operations to Make the Right Side Monotonically Non-Increasing

Similarly, to make the right side \(k \dots N+1\) monotonically non-increasing (which is monotonically non-decreasing when viewed from right to left) and set the peak \(k\) to height \(H'_k\), the minimum number of operations \(C_R(H'_k)\) can be expressed using the cumulative sum of decreases from the right side as follows: $\(C_R(H'_k) = D_k - H'_k\)\( Here, \)Dk\( is the sum of the "decreases" (\)H{i-1} - H_i > 0\() in the original sequence from index \)k\( to \)N+1$.

4. Combining Left and Right Operations (Sharing Operations)

The operations for making the left side monotonically non-decreasing and the right side monotonically non-increasing can be shared (combined) by simultaneously decrementing intervals \([l, r]\) that span across the peak \(k\) (\(l \le k \le r\)). The maximum number of operations that can be shared is bounded by the amount we lower the peak \(k\) from its original height \(H_k\) to \(H'_k\) (which is \(H_k - H'_k\)). Therefore, the overall minimum number of operations \(\text{Cost}(H'_k)\) is given by: $\(\text{Cost}(H'_k) = C_L(H'_k) + C_R(H'_k) - \min(H_k - H'_k, C_L(H'_k), C_R(H'_k))\)$

Substituting \(C_L(H'_k) = L_k - H'_k\) and \(C_R(H'_k) = D_k - H'_k\) into this equation and simplifying, the term inside the \(\min\) is always \(H_k - H'_k\), and the formula becomes extremely simple: $\(\text{Cost}(H'_k) = L_k + R_k - H'_k\)\( (Note that \)R_k = D_k - H_k\(, which corresponds to the sum of increases in \)k \dots N+1$)

5. Determining \(H'_k\)

To minimize the cost, we should make the subtracted term \(H'_k\) as large as possible. However, since the number of operations must be non-negative and we cannot make the peak higher than its original height, the following constraints must be satisfied: - \(H'_k \le H_k\) - \(H'_k \le L_k\) (since \(C_L(H'_k) \ge 0\)) - \(H'_k \le D_k\) (since \(C_R(H'_k) \ge 0\))

Therefore, the optimal value of \(H'_k\) is \(min\_val = \min(\{H_k, L_k, D_k\})\), and the minimum cost for this \(k\) is \(L_k + R_k - min\_val\).

---

Algorithm

1. Prepend and append \(H_0 = 0\) and \(H_{N+1} = 0\) to the sequence.
2. Calculate the increase \(A_i = \max(0, H_i - H_{i-1})\) and decrease \(B_i = \max(0, H_{i-1} - H_i)\) for each adjacent pair.
3. Precompute the prefix sums \(sumA\) and \(sumB\) of \(A_i\) and \(B_i\). This allows us to obtain the following values in \(O(1)\) for any \(k\):
   • \(L_k = sumA[k]\)
   • \(R_k = sumA[N+1] - sumA[k]\)
   • \(D_k = sumB[N+1] - sumB[k]\)
4. Loop \(k\) from \(1\) to \(N\), and find the minimum value of the cost \(L_k + R_k - \min(\{H_k, L_k, D_k\})\) over all \(k\).

---

Complexity

• Time Complexity: \(O(N)\) Constructing the prefix sums takes \(O(N)\) time, and searching for each \(k\) takes \(O(1)\) time, so the overall algorithm runs in linear time \(O(N)\).
• Space Complexity: \(O(N)\) It uses \(O(N)\) memory to store the original array and the prefix sum arrays.

---

Implementation Points

• The height \(H_i\) can be up to \(10^9\), and the maximum value of the prefix sums can reach around \(10^{15}\). To prevent overflow, you should use the long long type in C++.

• Since the input size \(N = 10^6\) is very large, it is recommended to include fast I/O optimizations such as std::cin.tie(NULL).

  Source Code

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    // 高速な入出力
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    if (!(cin >> N)) return 0;

    vector<long long> H(N + 2, 0);
    for (int i = 1; i <= N; ++i) {
        cin >> H[i];
    }
    H[0] = 0;
    H[N + 1] = 0;

    vector<long long> A(N + 2, 0);
    vector<long long> B(N + 2, 0);
    for (int i = 1; i <= N + 1; ++i) {
        A[i] = max(0LL, H[i] - H[i - 1]);
        B[i] = max(0LL, H[i - 1] - H[i]);
    }

    vector<long long> sumA(N + 2, 0);
    vector<long long> sumB(N + 2, 0);
    for (int i = 1; i <= N + 1; ++i) {
        sumA[i] = sumA[i - 1] + A[i];
        sumB[i] = sumB[i - 1] + B[i];
    }

    long long min_cost = -1;
    for (int k = 1; k <= N; ++k) {
        long long L_k = sumA[k];
        long long R_k = sumA[N + 1] - sumA[k];
        long long D_k = sumB[N + 1] - sumB[k];
        long long min_val = min({H[k], L_k, D_k});
        long long cost = R_k + L_k - min_val;
        if (min_cost == -1 || cost < min_cost) {
            min_cost = cost;
        }
    }

    cout << min_cost << "\n";

    return 0;
}

---

This editorial was generated by gemini-3.5-flash-high.