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

vector<array<int, 2>> norm(const vector<array<int, 2>>& arr) {
    vector<array<int, 2>> ans;
    for (auto elem : arr) {
        if (!ans.empty() && elem[1] >= ans.back()[1]) continue;
        while (!ans.empty() && ans.back()[0] == elem[0] && ans.back()[1] >= elem[1]) ans.pop_back();
        ans.push_back(elem);
    }
    return ans;
}

array<int, 2> get_max(array<int, 2> a, array<int, 2> b) {
    return {max(a[0], b[0]), max(a[1], b[1])};
}

vector<array<int, 2>> apply(vector<array<int, 2>> arr, int mid, int val) {
    array<int, 2> mx = {0, 0};
    if (val > mid) {
        mx[0] = val - mid;
    } else {
        mx[1] = mid - val;
    }
    for (auto& elem : arr) {
        elem = get_max(elem, mx);
    }
    return norm(arr);
}

vector<array<int, 2>> mrg(vector<array<int, 2>> a, vector<array<int, 2>> b) {
    vector<array<int, 2>> ans;
    int idb = -1;
    for (int i = 0; i < (int)a.size(); ++i) {
        while (idb + 1 < (int)b.size() && b[idb + 1][0] <= a[i][0]) {
            ++idb;
            if (i != 0) {
                ans.push_back(get_max(a[i - 1], b[idb]));
            }
        }
        if (idb != -1) {
            ans.push_back(get_max(a[i], b[idb]));
        }
    }
    return norm(ans);
}

vector<array<int, 2>> get_max(vector<array<int, 2>> a, vector<array<int, 2>> b) {
    vector<array<int, 2>> res;
    merge(a.begin(), a.end(), b.begin(), b.end(), back_inserter(res));
    return norm(res);
}

array<vector<array<int, 2>>, 4> solve(int mid, const vector<int>& a, int l, int r) {
    array<vector<array<int, 2>>, 4> ans;
    if (r - l == 1) {
        ans[0].push_back({0, 0});
        ans[1] = ans[2] = ans[0];
        ans[3] = apply(ans[0], mid, a[l]);
        return ans;
    }
    int m = (l + r) / 2;
    auto res1 = solve(mid, a, l, m);
    auto res2 = solve(mid, a, m, r);
    for (int mask = 0; mask < 4; ++mask) {
        int maskl = mask & 1;
        int maskr = mask & 2;
        vector<array<int, 2>> p = mrg(res1[maskl + 2], res2[maskr + 1]);
        vector<array<int, 2>> q = apply(mrg(res1[maskl], res2[maskr]), mid, a[m - 1] + a[m]);
        ans[mask] = get_max(p, q);
    }
    return ans;
}

const int INF = 2e9 + 1000;

int solve(int mid, vector<int> a) {
    auto res = solve(mid, a, 0, a.size());
    int opt = INF;
    for (auto elem : res[3]) {
        if (elem[0] < INF - elem[1]) {
            opt = min(opt, elem[0] + elem[1]);
        }
    }
    return opt;
}

void solve_() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    if (n <= 2) {
        cout << "0\n";
        return;
    }
    cout << min(solve(a[0], vector<int>(a.begin() + 1, a.end()))
                , solve(a[0] + a[1], vector<int>(a.begin() + 2, a.end()))) << "\n";
}

#define MULTITEST

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int tst = 1;
#ifdef MULTITEST
    cin >> tst;
#endif // MULTITEST
    while (tst--) {
        solve_();
    }
    return 0;
}