Description：

把 $n$ 个数分组，每组一到两个，最小化每组权值和的极差。

$1\leqslant n\leqslant 10^6$

Solution：

首先一个暴力的做法是枚举最小值，然后可以 $DP$ 求出可行的最大值，再判断，这样做是 $O(n^2)$ 的，我们可以把所有长度为 $1$ 或 $2$ 的区间都取出来，然后问题就变成了选出极差最小的区间集合覆盖整个线段，这就可以用线段树维护，具体来说维护 $m,lm,mr,lr$ 表示不包括左右端点，不包括右端点，不包括左端点，两个端点都包括的最小的最大权值，之所以要维护最小距离是因为要从大往小加入这些区间，然后每次加入区间的时候更新一下线段树，然后再更新答案就行了。

注意如果区间长度为 $1$ 的时候有很多特殊的情况在 $pushup$ 的时候要特别注意。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n;

#define MAXN 100010

typedef long long ll;

ll a[MAXN];

struct seg

{

	int l,r;

	ll v;

}s[MAXN << 1];

bool cmp_val(seg a,seg b){return a.v > b.v;}

int tot = 0;

#define INF 0x3f3f3f3f3f3f3f3f

struct node

{

	int lc,rc;

	ll m,lm,mr,lr;

	void init(){m = lm = mr = lr = INF;}

}t[MAXN << 1];

int ptr = 0;

int newnode()

{

	t[++ptr].init();

	return ptr;

}

int root;

#define mid ((l + r) >> 1)

void build(int &rt,int l,int r)

{

	rt = newnode();

	if(r - l + 1 == 2)t[rt].m = -INF;

	if(l == r)

	{

		t[rt].m = t[rt].lm = t[rt].mr = -INF;

		return;

	}

	build(t[rt].lc,l,mid);

	build(t[rt].rc,mid + 1,r);

	return; 

}

int now;

ll max(ll a,ll b,ll c){return max(a,max(b,c));}

void pushup(int rt,int l,int r)

{

	t[rt].lr = max(t[t[rt].lc].lr,t[t[rt].rc].lr);

	t[rt].lm = max(t[t[rt].lc].lr,t[t[rt].rc].lm);

	t[rt].mr = max(t[t[rt].lc].mr,t[t[rt].rc].lr);

	t[rt].m = max(t[t[rt].lc].mr,t[t[rt].rc].lm);

	ll val = a[mid] + a[mid + 1];

	if(val >= now)

	{

		if(r - l + 1 == 2)t[rt].lr = min(t[rt].lr,val);

		else

		{

			if(r - l + 1 >= 4)

			{

				t[rt].lm = min(t[rt].lm,max(t[t[rt].lc].lm,val,t[t[rt].rc].m));

				t[rt].mr = min(t[rt].mr,max(t[t[rt].lc].m,val,t[t[rt].rc].mr));

				t[rt].m = min(t[rt].m,max(t[t[rt].lc].m,val,t[t[rt].rc].m));

				t[rt].lr = min(t[rt].lr,max(t[t[rt].lc].lm,val,t[t[rt].rc].mr));

			}

			else

			{

				t[rt].mr = min(t[rt].mr,max(t[t[rt].lc].m,val,t[t[rt].rc].mr));

				t[rt].lr = min(t[rt].lr,max(t[t[rt].lc].lm,val,t[t[rt].rc].mr));

			}

		}

	}

	return;

}

void add1(int rt,int p,int l,int r)

{

	if(l == r)

	{

		t[rt].lr = a[p];

		return;

	}

	if(p <= mid)add1(t[rt].lc,p,l,mid);

	else add1(t[rt].rc,p,mid + 1,r);

	pushup(rt,l,r);

	return;

}

void add2(int rt,int p,int l,int r)

{

	if(p + 1 <= mid)add2(t[rt].lc,p,l,mid);

	else if(p > mid)add2(t[rt].rc,p,mid + 1,r);

	pushup(rt,l,r);

	return;

}

void work()

{

	scanf("%d",&n);

	for(int i = 1;i <= n;++i)scanf("%lld",&a[i]);

	ptr = 0;

	build(root,1,n);

	tot = 0;

	for(int i = 1;i <= n;++i)s[++tot] = (seg){i,i,a[i]};

	for(int i = 1;i < n;++i)s[++tot] = (seg){i,i + 1,a[i] + a[i + 1]};

	sort(s + 1,s + 1 + tot,cmp_val);

	ll ans = INF;

	for(int i = 1;i <= tot;++i)

	{//cout << s[i].l << " " << s[i].r << " " << s[i].v << endl;

		now = s[i].v;

		if(s[i].l == s[i].r)

		{

			add1(root,s[i].l,1,n);

			ans = min(ans,t[root].lr - s[i].v);

		}

		else

		{

			add2(root,s[i].l,1,n);

			if(t[root].lr != INF)ans = min(ans,t[root].lr - s[i].v);

		}//cout << s[i].v << " " << t[root].lr << endl;

	}

	cout << ans << endl;

	return;

}

int main()

{

	int testcases;

	scanf("%d",&testcases);

	while(testcases--)work();

	return 0;

}