#include<bits/stdc++.h>
#define rep(i,j,k) for(int i=j;i<=k;i++)
#define repp(i,j,k) for(int i=j;i>=k;i--)
#define ls(x) (x<<1)
#define rs(x) ((x<<1)|1)
#define mp make_pair
#define sec second
#define fir first
#define pii pair<int,int>
#define lowbit(i) i&-i
#define double long double
#define int long long
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N=2e5+5,M=1005,S=105,inf=(ll)1e18+7,mo=1e9+7;
const double eps=1e-8;
void read(int &p){
	int x=0,w=1;
	char ch=0;
	while(!isdigit(ch)){
		if(ch=='-')w=-1;
		ch=getchar();
	}
	while(isdigit(ch)){
		x=(x<<1)+(x<<3)+ch-'0';
		ch=getchar();
	}
	p=x*w;
}
int TT;
int n,a[N];
int nlim=0;
struct node{
    int le,ri;
    int v[2][2];
    friend node operator+(node x,node y){
        node res;
        res.le=x.le,res.ri=y.ri;
        rep(i,0,1){
            rep(j,0,1){
                int val=inf;
                val=min(val,max(x.v[i][0],y.v[0][j]));
                if(a[x.ri]+a[y.le]>=nlim)val=min(val,max({x.v[i][1],y.v[1][j],a[x.ri]+a[y.le]}));
                res.v[i][j]=val;
            }
        }
        return res;
    }
};
struct seg{
    node t[N*4];
    void pushup(int x){
        t[x]=t[ls(x)]+t[rs(x)];
    }
    void modify(int x,int le,int ri,int p){
        if(le==ri){
            t[x].le=t[x].ri=le;
            t[x].v[1][1]=inf;
            if(a[le]>=nlim)t[x].v[0][0]=a[le];
            else t[x].v[0][0]=inf;
            t[x].v[0][1]=t[x].v[1][0]=0;
            return;
        }
        int mid=(le+ri)>>1;
        if(p<=mid)modify(ls(x),le,mid,p);
        else modify(rs(x),mid+1,ri,p);
        pushup(x);
    }
}T;
struct sit{
    int val,x,y;
    friend bool operator<(sit x,sit y){
        return x.val<y.val;
    }
}s[N];
void solve(){
    read(n),nlim=0;
    rep(i,1,n)
        read(a[i]),s[i]=(sit){a[i],i,0};
    rep(i,1,n-1)
        s[i+n]=(sit){a[i]+a[i+1],i,i+1};
    sort(s+1,s+n*2);
    rep(i,1,n)
        T.modify(1,1,n,i);
    int ans=inf;
    rep(i,1,2*n-1){
        nlim=s[i].val;
        if(s[i].val!=s[i-1].val)ans=min(ans,T.t[1].v[0][0]-nlim);
        nlim++;
        if(s[i].x)T.modify(1,1,n,s[i].x);
        if(s[i].y)T.modify(1,1,n,s[i].y);
    }
    printf("%lld\n",ans);
}
signed main(){
    read(TT);
    while(TT--)
        solve();
    return 0;
}