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

int n, t;

int run(vector<int> a){
    int n = a.size();
    int m = 0;
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
        for(int j = 0 ; j < n; j++){
            pq.push(make_pair(a[j], j));
            m = max(a[j], m);
        }
        pq.push(make_pair(INT_MAX, 0));

        pair<int, int> f = pq.top();
        pq.pop();
        int l, r;
        l = r = f.second;
        int biggestIn = f.first;
        int smallestIn = f.first;
        int val = f.first;
        int ans = m - smallestIn;
        while(!pq.empty()){
            while(pq.top().first == val){
                pair<int, int> curr = pq.top();
                pq.pop();
                for(int j = l ; j >= curr.second; j--){
                    biggestIn = max(biggestIn, a[j]);
                }
                for(int j = r; j <= curr.second; j++){
                    biggestIn = max(biggestIn, a[j]);
                }
                l = min(l, curr.second);
                r = max(r, curr.second);
            }
            if(pq.top().first == INT_MAX){
                break;
            }
            int pos = max(biggestIn - smallestIn, m - pq.top().first);
            ans = min(pos, ans);
            pair<int, int> curr = pq.top();
            pq.pop();
            for(int j = l ; j >= curr.second; j--){
                biggestIn = max(biggestIn, a[j]);
            }
            for(int j = r; j <= curr.second; j++){
                biggestIn = max(biggestIn, a[j]);
            }
            l = min(l, curr.second);
            r = max(r, curr.second);
            val = curr.first;
        }

        return ans;
}

int main(){
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cin >> t;
        while(t--){
            cin >> n;
            vector<int> a(n, 10000000);
            vector<int> b(n, 10000000);
            int p = 0;
            for(int j = 0 ; j < n; j++){
                cin >> p;
                a[j] -= p;
                b[j] += p;
            }
            cout << min(run(a), run(b)) << '\n';
        }
}