首先這個查詢操作很迷，考慮先化簡查詢操作。

不難發現由于每次是加上一個逆的等差序列，因此一次操作完每個數與它的前驅之差一定會減少，因此加上等差序列的次數就等于全局每個數與它的前驅之差最大值。

又因為會排序去重，所以最后剩下來的數一定是最開始的數一路加過來的，至此我們發現答案就是全局每個數與它的前驅之差最大值加上全局最大值。

考慮怎么維護這個東西，顯然可以使用 FHQ treap 維護這件事，我們需要維護子樹最大差，最小值，最大值就可以合并信息，在點修時先把原來的數刪掉，在插入新的數。

時間復雜度 \(O(n \log n)\)。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5+114;
int n,q;
int a[maxn];
struct Node{
	int val,ls,rs,w,mx,mi,ans;
}treap[maxn];
stack<int> brush;
int tot;
int rt;
int clone(int w){
	int New;
    if(brush.size()>0) New=brush.top(),brush.pop();
    else New=++tot;
	treap[New].val=rand();
	treap[New].ls=0;
	treap[New].rs=0;
	treap[New].w=w;
	treap[New].mi=treap[New].mx=w;
	treap[New].ans=0;
	return New;
}
inline void pushup(int cur){
	treap[cur].ans=0;
	treap[cur].ans=max(treap[treap[cur].ls].ans,treap[treap[cur].rs].ans);
	if(treap[cur].ls!=0) treap[cur].ans=max(treap[cur].w-treap[treap[cur].ls].mx,treap[cur].ans);
	if(treap[cur].rs!=0) treap[cur].ans=max(treap[treap[cur].rs].mi-treap[cur].w,treap[cur].ans);
	treap[cur].mx=treap[cur].mi=treap[cur].w;
	if(treap[cur].rs!=0) treap[cur].mx=treap[treap[cur].rs].mx;
	if(treap[cur].ls!=0) treap[cur].mi=treap[treap[cur].ls].mi;
}
inline int merge(int x,int y){
    if(!x||!y) return x+y;
    if(treap[x].val<treap[y].val){
        treap[x].rs=merge(treap[x].rs,y);
        pushup(x);
        return x;
    }
    else{
        treap[y].ls=merge(x,treap[y].ls);
        pushup(y);
        return y;
    }
}
inline void split(int cur,int x,int &l,int &r) {
	if(cur==0){
		l=r=0;
		return ;
	}
	if(treap[cur].w>x){
		r=cur;
		split(treap[cur].ls,x,l,treap[cur].ls);
	}
	else{
		l=cur;
		split(treap[cur].rs,x,treap[cur].rs,r);
	}
	pushup(cur);
}
void dfs(int u){
	if(u==0) return ;
	dfs(treap[u].ls);
	cout<<treap[u].w<<' '<<treap[u].mx<<' '<<treap[u].mi<<'\n';
	dfs(treap[u].rs);
}
void insert(int w){
	int x=0,y=0,z=0;
	split(rt,w,x,z);
	y=clone(w);
	rt=merge(x,merge(y,z));
}
void erase(int w){
	int x=0,y=0,z=0;
	split(rt,w-1,x,y);
	split(y,w,y,z);
    brush.push(y);
	y=merge(treap[y].ls,treap[y].rs);
	rt=merge(x,merge(y,z));
}
void work(){
	rt=tot=0;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		insert(a[i]); 
	}
	cin>>q;
	while(q--){
		int x,y;
		cin>>x>>y;
		erase(a[x]);
		a[x]=y;
		insert(a[x]);
		cout<<treap[rt].mx+treap[rt].ans<<' ';
	}
	cout<<'\n';
}
int T;
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>T;
	while(T--)work();
}