#include <cstdio>
#include <algorithm>
#define lc (p<<1)
#define rc (p<<1|1)
using namespace std;
int read(){
	char c=getchar();int x=0;bool f=0;
	while(c<48||c>57) f|=(c=='-'),c=getchar();
	do x=(x<<1)+(x<<3)+(c^48),c=getchar();
	while(c>=48&&c<=57);
	if(f) return -x;
	return x;
}
typedef long long ll;
const ll INF=0x3f3f3f3f3f3f3f3f;
const int N=100003;
struct Mat{
	ll f[2][2];
	friend Mat operator*(const Mat A,const Mat B){
		Mat C;
		C.f[0][0]=min(max(A.f[0][0],B.f[0][0]),max(A.f[0][1],B.f[1][0]));
		C.f[0][1]=min(max(A.f[0][0],B.f[0][1]),max(A.f[0][1],B.f[1][1]));
		C.f[1][0]=min(max(A.f[1][0],B.f[0][0]),max(A.f[1][1],B.f[1][0]));
		C.f[1][1]=min(max(A.f[1][0],B.f[0][1]),max(A.f[1][1],B.f[1][1]));
		return C;
	}
	void init(){f[0][0]=f[1][1]=f[1][0]=INF;f[0][1]=-INF;}
}sg[N<<2];
struct node{
	int w,p,t;
	friend bool operator<(const node a,const node b){
		return a.w>b.w;
	}
}s[N<<1];
int n,rk;
int a[N];
void build(int p=1,int l=1,int r=n){
	if(l==r) return sg[p].init();
	int mid=(l+r)>>1;
	build(lc,l,mid);
	build(rc,mid+1,r);
	sg[p]=sg[lc]*sg[rc];
}
void update(node x,int p=1,int l=1,int r=n){
	if(l==r){sg[p].f[x.t][0]=x.w;return;}
	int mid=(l+r)>>1;
	if(x.p<=mid) update(x,lc,l,mid);
	else update(x,rc,mid+1,r);
	sg[p]=sg[lc]*sg[rc];
}
void solve(){
	n=read();rk=0;
	for(int i=1;i<=n;++i){
		a[i]=read();
		s[++rk]=(node){a[i],i,0};
		if(i>1) s[++rk]=(node){a[i]+a[i-1],i,1};
	}
	build();sort(s+1,s+rk+1);
	ll mn=INF;
	for(int i=1;i<=rk;++i){
		update(s[i]);
		mn=min(mn,max(sg[1].f[0][0],sg[1].f[0][1])-s[i].w);
	}
	printf("%lld\n",mn);
}
int main(){
	int tc=read();
	while(tc--) solve();
	return 0;
}