#include <iostream>
#define int long long

using namespace std;

const int N=2e5+5,mod=1e9+7;

int t,n,a[N],b[N],ans;

int qpow(int x,int k){
	int v=1;
	while (k){
		if (k&1) v=v*x%mod;
		x=x*x%mod,k>>=1;
	}
	return v;
}

bool check(){
	int c1=0,v=n&1?1:-1;
	for (int i=n;i;i--,v=-2*v%mod)
		c1=(c1+v*b[i])%mod;
	v=-v;
	c1=(c1*qpow(n&1?v+1:v-1,mod-2)%mod+mod)%mod;
	b[1]-=2*c1,b[n]-=c1;
	if (b[1]<0||b[n]<0) return 0;
	for (int i=2;i<=n;i++){
		b[i]-=2*b[i-1];
		if (b[i]<0) return 0;
	}
	return 1;
}

signed main(){
	ios::sync_with_stdio(0),cin.tie(0);
	cin>>t;
	while (t--){
		cin>>n;
		for (int i=1;i<=n;i++) cin>>a[i];
		int l=-1,r=5e8;
		while (l+1^r){
			int mid=l+r>>1;
			for (int i=1;i<=n;i++)
				b[i]=a[i]-3*mid;
			(check()?l:r)=mid;
		}
		ans=3*l,l=-1,r=5e8;
		while (l+1^r){
			int mid=l+r>>1;
			for (int i=1;i<=n;i++)
				b[i]=a[i]-3*mid+1;
			(check()?l:r)=mid;
		}
		ans=max(ans,3*l-1),l=-1,r=5e8;
		while (l+1^r){
			int mid=l+r>>1;
			for (int i=1;i<=n;i++)
				b[i]=a[i]-3*mid+2;
			(check()?l:r)=mid;
		}
		ans=max(ans,3*l-2);
		cout<<max(0ll,ans)<<"\n";
	}
	return 0;
}