#include <bits/stdc++.h>
#define int long long

using namespace std;

const int MOD = 1e9 + 7;

void solve(){
	int n;
	cin >> n;
	vector<int> a(n);
	int ma = 0, mi = LLONG_MAX;
	
	for(int i = 0; i < n; i++){
		cin >> a[i];
		ma = max(ma, a[i]);
		mi = min(mi, a[i]);
	}
	vector<int> tmp(a.begin(), a.end());
	
	int s = mi, e = ma;
	int ans = ma - mi;
	while(s <= e){
		int mid = s + (e - s) / 2;
		vector<pair<int,int>> cnt;
		int mi1 = LLONG_MAX;
		vector<int> b(a.begin(), a.end());
		
		for(int i = 0; i < n; i++){
			if(b[i] > mid){
				cnt.push_back({b[i] - mid, i});
				b[i] = mid;
			}
			while(b[i] < mid && cnt.size()){
				if(cnt.back().first + b[i] > mid){
					cnt.back().first -= mid - b[i];
					b[i] = mid;
					break;
				}else{
					b[i] += cnt.back().first;
					cnt.pop_back();
				}
			}
			mi1 = min(mi1, b[i]);
			
		}
		
		if(cnt.size()){
			s = mid + 1;
		}else{
			
			ma = min(ma, mid);
			tmp = b;
			e = mid - 1;
		}
		
	}
	
	int ss = mi, ee = ma;
	

	while(ss <= ee){
		int midd = ss + (ee - ss) / 2;
		vector<int> b(tmp.begin(), tmp.end());
		int idx = -1;
		bool pos = true;
		for(int i = 0; i < n; i++)if(b[i] >= ma)idx = i;
		vector<pair<int, int>> ext;
		
		for(int i = 0; i< n && pos; i++){
			if(i == idx){
				if(b[i] > ma){
					ext.push_back({b[i] - ma, i});
				}
				continue;
			}
			if(b[i] > midd){
				ext.push_back({b[i] - midd, i});
				b[i] = midd;
			}
			while(b[i] < midd && ext.size()){
				if(ext.back().first + b[i] > midd){
					ext.back().first -= midd - b[i];
					b[i] = midd;
				}else{
					b[i] += ext.back().first;
					ext.pop_back();
				}
			}
			if(b[i] < midd)pos = false;
		}
		
		if(pos && (!ext.size() || ext.back().second != idx)){
			mi = max(mi, midd);
			ss = midd + 1;
		}else{
			ee = midd - 1;
		}
	}

	cout << ma - mi << "\n";
}

int32_t main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int t = 1;
	cin >> t;
	
	for(int i = 1; i <= t; i++){
		solve();
	}
	return 0;
}