#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <bitset>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <cassert>

const int N = 3e5 + 7;
using namespace std;
long long n, a[N], m, ans[N], dp[N][2], dp2[N][2];

bool maxim(long long& a, long long val) {
    if (a < val) {
        a = val;
        return 1;
    }
    return 0;
}

void solve() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        dp[i][0] = 0;
        dp[i][1] = 0;
        dp2[i][0] = 1e18;
        dp2[i][1] = 1e18;
    }
    dp[0][0] = 0;
    dp[0][1] = 0;
    dp2[0][0] = 0;
    dp2[0][1] = 0;
    for (int i = 1; i < n; i++) {
        if (maxim(dp[i][1], dp[i - 1][0] + 1)) {
            int mx = max(a[i - 1], a[i + 1]);
            int add = max(0LL, mx - a[i] + 1);
            dp2[i][1] = dp2[i - 1][0] + add;
        }
        if (dp[i][1] == dp[i - 1][0] + 1) {
            int mx = max(a[i - 1], a[i + 1]);
            int add = max(0LL, mx - a[i] + 1);
            dp2[i][1] = min(dp2[i - 1][0] + add, dp2[i][1]);
        }
        if (maxim(dp[i][0], dp[i - 1][0])) {
            dp2[i][0] = dp2[i - 1][0];
        }
        if (dp[i][0] == dp[i - 1][0]) {
            dp2[i][0] = min(dp2[i - 1][0], dp2[i][0]);
        }
        if (maxim(dp[i][0], dp[i - 1][1])) {
            dp2[i][0] = dp2[i - 1][1];
        }
        if (dp[i][0] == dp[i - 1][1]) {
            dp2[i][0] = min(dp2[i - 1][1], dp2[i][0]);
        }
    }
    cout << dp2[n - 1][0] << "\n";
}

signed main()
{
#ifdef _DEBUG
    freopen("input.txt", "r", stdin);
#else
    std::ios::sync_with_stdio(false);
    cin.tie(0);
#endif

    int t;
    cin >> t;
    while (t--) {
        solve();
    }
}