Code : Chip and Ribbon

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

long long solve(vector<long long> &a) {
    int n = a.size();
    vector<long long> dp(n, 0);
    // dp[i] is the number of teleports that start at index i.

    // Idea: Don't apply the first move at all. Hence, every element would use
    // a[i] teleports.
    // Then, a teleport can freely slide to the right as long as
    // a[i + 1] >= a[i].
    dp[0] = a[0];
    for (int i = 1; i < n; i++) {
        // If this element is smaller, it doesn't have to worry, all the
        // teleports would flow freely to the right.
        if (a[i] <= a[i - 1]) {
            dp[i] = 0;
        } else {
            dp[i] = a[i] - a[i - 1];
        }
    }

    // Removing 1 teleport for a[0].
    return accumulate(dp.begin(), dp.end(), 0LL) - 1;
}

int main() {
    int t;
    cin >> t;

    for (int zz = 0; zz < t; zz++) {
        int n;
        cin >> n;
        vector<long long> a(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }

        long long res = solve(a);
        cout << res << "\n";
    }
}