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

#define F first
#define S second
#define ar array
typedef int uci;
#define int long long
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define ll long long
typedef pair<int, int> pii;
typedef vector<int> vi;

void solve(){
    ll N; cin >> N;
    vi A(N); rep(i,0,N) cin >> A[i];

    ll M = A[0], m = A[0];

    rep(i,0,N) {M = max(M,A[i]); m = min(m,A[i]);}

    map<ll, vi> indices;
    rep(i,0,N) indices[A[i]].push_back(i);


    vi uA; for(auto kv:indices) uA.push_back(kv.first);


    ll ans = M-m;



    ll maxr = -1;
    ll l = N+1;
    ll r = -1;
    for(auto m2: uA) {

        ll ol = l, olr=r;
        for(auto i: indices[m2]) {l = min(l,i); r = max(r, i);}

        if(olr<0) {
            rep(i,l,r+1) maxr = max(maxr, A[i]);
        } else {
            rep(i,l,ol) maxr = max(maxr, A[i]);
            rep(i,olr+1,r+1) maxr = max(maxr, A[i]);
        }

        if(maxr + m2 - m + 1 > M) break;

        ll incr = M - maxr;

        ans = M-min(m+incr,m2+1);
    }
    nextl1:

    ll minr = M+1;
    l = N;
    r = -1;
    reverse(uA.begin(), uA.end());
    for(auto M2: uA) {
        ll ol = l, olr=r;
        for(auto i: indices[M2]) {l = min(l,i); r = max(r, i);}

        if(olr<0) {
            rep(i,l,r+1) minr = min(minr,A[i]);
        } else {
            rep(i,l,ol) minr = min(minr,A[i]);
            rep(i,olr+1,r+1) minr = min(minr,A[i]);
        }

        if(minr - (M-M2+1) < m) break;

        ll decr = minr-m;

        ans = min(ans, max(M2-1, M-decr)-m);
    }

    nextl2:

    cout << ans << '\n';

}

uci main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    ll T; cin >> T;
    rep(t,0,T) solve();
}