#include <bits/stdc++.h>

#pragma GCC optimize("O3")
#define int long long

using namespace std;

#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()
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef vector<int> vi;

bool is_possible2(vector<int> a, int l, int r, int d) {
	if (r - l > d) return false;
	if (a.empty()) return true;
	int mx = *max_element(a.begin(), a.end());
	int mn = *min_element(a.begin(), a.end());
	
	
	vector<int> haveto(a.size());
	int sm = 0;
	for (int i = 0; i < a.size(); ++i) {
		haveto[i] = max(mx, r) - d > a[i];
		sm += haveto[i];
	}

	if (sm == 0) return true;

	int ls = a.size();
	int rs = 0;
	for (int i = 0; i < a.size(); ++i) if (haveto[i]) {
		ls = min(ls, i);
		rs = max(rs, i);
	}

	int diff = max(mx, r) - d - mn;

	for (int i = ls; i <= rs; ++i) a[i] += diff;

	mx = *max_element(a.begin(), a.end());
	mn = *min_element(a.begin(), a.end());

	return max(mx, r) - min(mn, l) <= d;
}

bool is_possible(vector<int> a, int d) {
	int n = a.size();
	int mx = *max_element(a.begin(), a.end());
	vector<vector<int>> segments;
	vector<int> cur;
	multiset<int> elements;
	for (int v : a) if (v == mx) {
		segments.push_back(cur);
		cur = vector<int>();
	} else {
		cur.push_back(v);
		elements.insert(v);
	}
	elements.insert(mx);
	segments.push_back(cur);
	for (vector<int> seg : segments) {
		for (int v : seg) elements.extract(v);
		int upper = *elements.rbegin();
		int lower = *elements.begin();

		if (is_possible2(seg, lower, upper, d)) return true;

		for (int v : seg) elements.insert(v);
	}
	return false;
}

int solve(vector<int> a) {
	int l = 0, r = *max_element(a.begin(), a.end()) - *min_element(a.begin(), a.end());
	while (l < r) {
		int m = (l + r) / 2;
		if (is_possible(a, m)) r = m;
		else l = m + 1;
	}
	return l;
}

signed main(){
	cin.tie(0);
	ios::sync_with_stdio(0);
	int tc; cin >> tc;
	while (tc--) {
		int n; cin >> n;
		vector<int> a(n);
		for (int& v : a) cin >> v;
		int res = solve(a);
		for (int& v : a) v *= -1;
		res = min(res, solve(a));
		cout << res << '\n';
	}
}