#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);

    ll ans = M-m;

    ll ML = N+1, MR=-1; for(auto mi: indices[M]) {ML = min(ML, mi); MR = max(MR, mi);}
    ll mL = N+1, mR=-1; for(auto mi: indices[m]) {mL = min(mL, mi); mR = max(mR, mi);}


    ll maxr = -1;
    ll l = N+1;
    ll r = -1;
    for(ll m2 = m; m2 <= (M+m)/2; m2++) {

        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;

        ans = M-m2-1;
    }
    nextl1:

    ll minr = M+1;
    l = N;
    r = -1;
    for(ll M2 = M; M2 >= (M+m+1)/2; M2--) {
        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;

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

    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();
}