/*
   卫风·芄兰
芄兰之支,童子佩觿.
虽则佩觿,能不我知?
容兮遂兮,垂带悸兮.
芄兰之叶,童子佩韘.
虽则佩韘,能不我甲?
容兮遂兮,垂带悸兮.
*/
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define PII pair<int,int>
#define tul tuple<int,int,int>
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define rep_(i,a,b) for(int i=a;i>=b;--i)
#define all(x) x.begin(),x.end()
#define bp(x) __builtin_popcountll(x)
#define cy cout<<"YES"<<endl
#define cn cout<<"NO"<<endl
#define lc (rt<<1)
#define rc (rt<<1|1)
mt19937_64 rnd(time(0));
const int N=3e5+5,yyx=998244353;
vector<int> to[N];
int q,n,a[N],b[N];
inline int mod(int x){
  return (x%yyx+yyx)%yyx;
}
inline int cmin(int &x,int y){
  return x>y?x=y,1:0;
}
inline int cmax(int &x,int y){
  return x<y?x=y,1:0;
}
inline void solve(){
   cin>>n;
   multiset<int> s;
   set<int> st;
   map<int,int> mp;
   rep(i,1,n) cin>>a[i],b[i]=a[i],st.insert(a[i]),mp[a[i]]++;
   sort(b+1,b+1+n);
   int cnt=unique(b+1,b+1+n)-b-1;
   rep(i,2,cnt){
    s.insert(b[i]-b[i-1]);
   }
   cin>>q;
   rep(i,1,q){
    int id,x;cin>>id>>x;
    int old=a[id];a[id]=x;
    auto p=st.find(old),g=st.upper_bound(old);
    if(p!=st.begin()) --p;
    int y=*p,z=*g;
    if(mp[old]>=2) y=old;
    if(z<old) z=old;
    if(old>y&&mp[old]==1) s.extract(old-y);
    if(old<z&&mp[old]==1) s.extract(z-old);
    if(mp[old]>1){
        if(x>old&&old<z&&x<z) s.extract(z-old);
        if(x<old&&old>y&&x>y) s.extract(old-y);
    }
    int ok=0;
    if(x>y&&x<z) s.insert(z-x),s.insert(x-y),ok=1;
    else if(old>y&&old<z&&mp[old]==1) s.insert(z-y);
    if(old==y&&x>y&&mp[old]==1&&!mp[x]) s.extract(x-y);
    if(old==z&&z>x&&mp[old]==1&&!mp[x]) s.extract(z-x);
    if(mp[old]==1) st.erase(old),mp[old]--;
    else if(mp[old]>1) mp[old]--;
    mp[x]++;
    int j=*st.begin();
    st.insert(x);
    if(!ok){
        auto pp=st.find(x),gg=st.upper_bound(x);
        if(pp!=st.begin()) --pp;
        y=*pp,z=*gg;
        if(z<x) z=x;
        if(y==x){
            if(x<j) s.insert(j-x);
        }
        if(z>y&&mp[x]==1&&z!=x) s.extract(z-y);
        if(x>y&&mp[x]==1) s.insert(x-y);
        if(z>x&&mp[x]==1) s.insert(z-x);
    }
    int ma=0,mx=0;
    if(s.size()) ma=*s.rbegin();
    if(st.size()) mx=*st.rbegin();
    cout<<mx+ma<<" \n"[i==q];
   }
}
signed main(){
  cin.tie(0)->sync_with_stdio(0);
  //freopen("D://321//in.txt","r",stdin);
  //freopen("D://321//out.txt","w",stdout);
  int _=1;
  cin>>_;
  while(_--)
  solve();
  return 0;
}