RT，实在卡不动了，码风极其丑，勿喷。

感激不尽。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n,t,a[1000000],x,y,q,res[1000000],rep[1000000];
map<ll,ll>M;
map<ll,ll>ans;
set<ll>s,ss;
priority_queue<ll>Q,QQ;
void solve(){
	M.clear();
	ans.clear();
	s.clear();
	ss.clear();
	Q=priority_queue<ll>();
	QQ=priority_queue<ll>();
	for(int i=1;i<=n;i++){
		res[i]=a[i];
	}
	sort(a+1,a+n+1);
	for(int i=2;i<=n;i++){
		if(ans[a[i]-a[i-1]]==0){
			Q.push(a[i]-a[i-1]);
		}
		ans[a[i]-a[i-1]]++;//答案方案数 
	}
	for(int i=1;i<=n;i++){
		a[i]=res[i];
	}
	for(int i=1;i<=n;i++){
		M[a[i]]++;
		if(M[a[i]]==1){
			s.insert(a[i]);
			ss.insert(-a[i]);
		}
	}
	for(int i=1;i<=n;i++){
		QQ.push(a[i]);
		a[i]=res[i];
	}
	while(q--){
		ll x,y;
		cin>>x>>y;
		M[a[x]]--;
		if(M[a[x]]==0){//没有了，合并！ 删除小块答案，增加大块答案 
			ll hou=*(s.upper_bound(a[x]));
			ll qian=-(*(ss.upper_bound(-a[x])));
			if(ss.upper_bound(-a[x])!=ss.end()){//前面有数 
				ans[abs(a[x]-qian)]--; 
			}
			if(s.upper_bound(a[x])!=s.end()){//后面有数 
				ans[abs(hou-a[x])]--; 
			}
			if(s.upper_bound(a[x])!=s.end()&&ss.upper_bound(-a[x])!=ss.end()){//都有，可以合并  
				if(ans[abs(hou-qian)]==0){
					Q.push(abs(hou-qian));
				}
				ans[abs(hou-qian)]++;
			}
			s.erase(a[x]);
			ss.erase(-a[x]);
		}
		M[y]++;
		if(M[y]==1){//无中生有，可以分割 
			QQ.push(y);
			ll hou=*(s.upper_bound(y));
			ll qian=-(*(ss.upper_bound(-y)));
			if(ss.upper_bound(-y)!=ss.end()){//前面有数 
				if(ans[abs(y-qian)]==0){
					Q.push(abs(y-qian));
				}
				ans[abs(y-qian)]++; 
			}
			if(s.upper_bound(y)!=s.end()){//后面有数 
				if(ans[abs(hou-y)]==0){
					Q.push(abs(hou-y));
				}
				ans[abs(hou-y)]++; 
			}
			if(s.upper_bound(y)!=s.end()&&ss.upper_bound(-y)!=ss.end()){//都有，分割掉 
				ans[abs(hou-qian)]--;
			}
			s.insert(y);
			ss.insert(-y);
		}
		a[x]=y;
		while(1){
			if(ans[Q.top()]){
				while(1){
					if(M[QQ.top()]){
						cout<<Q.top()+QQ.top()<<"\n";
						break;
					}
					else{
						QQ.pop();
					}
				}
				break;
			}
			else{
				Q.pop();
			}
		}
	}
}
int main(){
	cin>>t;
	while(t--){
		scanf("%lld",&n);
		for(int i=1;i<=n;i++){
			scanf("%lld",&a[i]);
		}
		scanf("%lld",&q);
		solve();
	}
} 
/*
2
4
2 4 6 8
3
1 5
3 10
4 1

5
1 4 9 11 6
5
1 5
3 6
5 2
2 10
3 7
*/