不妨设 \(a\) 单调递增（无重复），显然如果 \(n\le 3\) 答案就是 \(0\)。
显然答案 \(k\) 具有可二分性。也就是说，当 \(k < k_0\) 时一定不存在合法的 \(x,y,z\)，当 \(k\ge k_0\) 时一定存在，\(k_0\) 就是答案。
因此二分答案，只需要验证答案 \(k\) 是否存在合法的 \(x,y,z\)。
为了覆盖到 \(a_1\)，且 \(x\) 尽量往大取（这样可以覆盖更多的 \(a_i\)），我们令 \(x=a_1+k\)。接下来一段区间的 \(a_i\) 会被 \([x-k,x+k]\) 覆盖，我们跳过这段区间，找到下一个未被覆盖的 \(a_i\)。类似于刚刚的思路，我们令 \(y=a_i+k\)，再找到下一个未被覆盖的 \(a_j\)，令 \(z=a_j+k\)。如果此时所有 \(a_i\) 都被覆盖了，那么就合法，否则不合法。
时间复杂度 \(\mathcal O(n\log w)\)，其中 \(w\) 为值域。
//By: OIer rui_er
#include <bits/stdc++.h>
#define rep(x,y,z) for(ll x=(y);x<=(z);x++)
#define per(x,y,z) for(ll x=(y);x>=(z);x--)
#define debug(format...) fprintf(stderr, format)
#define fileIO(s) do{freopen(s".in","r",stdin);freopen(s".out","w",stdout);}while(false)
using namespace std;
typedef long long ll;
mt19937 rnd(std::chrono::duration_cast<std::chrono::nanoseconds>(std::chrono::system_clock::now().time_since_epoch()).count());
ll randint(ll L, ll R) {
uniform_int_distribution<ll> dist(L, R);
return dist(rnd);
}
template<typename T> void chkmin(T& x, T y) {if(x > y) x = y;}
template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;}
const ll N = 2e5+5, inf = numeric_limits<ll>::max();
ll T, n, a[N];
bool check(ll M) {
ll x = a[1] + M, y = inf, z = inf;
rep(i, 1, n) {
if(abs(a[i] - x) <= M);
else if(y == inf) y = a[i] + M;
else if(abs(a[i] - y) <= M);
else if(z == inf) z = a[i] + M;
else if(abs(a[i] - z) <= M);
else return false;
}
return true;
}
int main() {
for(scanf("%lld", &T); T; T--) {
scanf("%lld", &n);
rep(i, 1, n) scanf("%lld", &a[i]);
sort(a+1, a+1+n);
n = unique(a+1, a+1+n) - a - 1;
if(n <= 3) {puts("0"); continue;}
ll L = 0, R = a[n] - a[1] + 1;
while(L < R) {
ll M = (L + R) >> 1;
if(check(M)) R = M;
else L = M + 1;
}
printf("%lld\n", L);
}
return 0;
}