#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=1e5+10;
struct node
{
	int l,r,v;
	friend bool operator <(const node&A,const node&B){return A.l==B.l?A.r<B.r:A.l<B.l;}
};
typedef set<node>::iterator iter;
struct odtree
{
	set<node>s; int res=0,nr=0;
	inline void clear(){s.clear(),res=0;}
	inline iter split(int pos)
	{
		auto it=s.lower_bound({pos,0,0});
		if(it!=s.end() && it->l==pos) return it;
		auto [l,r,v]=*(--it); s.erase(it);
		s.insert({l,pos-1,v});
		return s.insert({pos,r,v}).first;
	}
	inline void modify(int x,int y)
	{
		auto L=split(x),R=L;
		while(R!=s.end() && R->v<=y) R++; nr=prev(R)->r;
		for(auto it=L;it!=R;it++) res-=it->v*(it->r-it->l+1);
		s.erase(L,R),s.insert({x,nr,y}),res+=(nr-x+1)*y;
	}
}F,G;
int n,Q,Sum,Max,a[maxn];
inline void solve()
{
	cin>>n; F.s.insert({1,n,0}),G.s.insert({1,n,0});
	for(int i=1;i<=n;i++) cin>>a[i],F.modify(i,a[i]),G.modify(n-i+1,a[i]),Sum+=a[i],Max=max(Max,a[i]); cin>>Q;
	for(int i=1,x,y;i<=Q;i++) cin>>x>>y,a[x]+=y,Sum+=y,Max=max(Max,a[x]),F.modify(x,a[x]),G.modify(n-x+1,a[x]),cout<<F.res+G.res-Sum-n*Max<<'\n';
	F.clear(),G.clear(),Sum=Max=0;
}
signed main(){ios::sync_with_stdio(false);cin.tie(NULL);int T;cin>>T;while(T--)solve();}