//g++ m.cpp -o m -g -std=c++14 -O0 -Wall
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<set>
#include<vector>
#define LL long long
using namespace std;
int qd(){
    int rt=0;char c=getchar();
    while(c<'0'||c>'9')  c=getchar();
    while('0'<=c&&c<='9')  rt=(rt<<3)+(rt<<1)+c-48,c=getchar();
    return rt;
}
const int maxn=2e6+10,_maxn=2e6;
struct node{int t,v;};
bool operator<(const node &x,const node &y){return x.t<y.t;}
set<node>f;
set<int>tn[maxn];
int N,a[maxn];LL ans=0;//7 5 3  -> 7 6 (5) 3   no 7 (5) 4 3
node backf(){auto it=f.end();if(it!=f.begin())  return *--it;else return {1,1};}
void calc(int t){
    auto it=f.lower_bound({t,0});
    if(it->t!=t){
        it=f.insert(it,(node){t,a[t]});
        auto l=it,r=it;l--,r++;
        ans+=1LL*(r->t-it->t)*(it->v-l->v);
    }
    else{
        auto r=it;r++;
        ans+=1LL*(r->t-it->t)*(a[t]-it->v);
        f.erase(it);
        it=f.insert({t,a[t]}).first;
    }
    auto l=it,r=it;l--,r++;
    if(l->v<=it->v){
        ans-=1LL*(r->t-it->t)*(it->v-l->v);
        f.erase(it);
    }
    else if(r->t!=N+1&&it->v<=r->v){
        l=r=it=r;l--,r++;
        ans-=1LL*(r->t-it->t)*(it->v-l->v);
        f.erase(it);
    }
}
int main(){
    //freopen("a.in","r",stdin);
    //freopen("a.out","w",stdout);
    N=qd();
    for(int i=1;i<=N;i++)  a[i]=qd();
    f.insert({0,_maxn});ans=-_maxn;
    for(int i=1;i<=N+1;i++){
        if(a[i]<backf().v)  ans+=1LL*backf().v*(i-backf().t),f.insert({i,a[i]});
        if(a[i])  tn[a[i]].insert(i);
    }
    if(backf().t!=N+1)  f.insert({N+1,0});
    printf("%lld\n",ans);
    int Q=qd();
    while(Q--){
        int t=qd(),v=qd()+1,_av=a[v];a[v]+=t==1?1:-1;
        if(_av)  tn[_av].erase(tn[_av].find(v));
        if(a[v])  tn[a[v]].insert(tn[a[v]].upper_bound(v),v);
        calc(v);
        auto it=tn[_av].upper_bound(v);
        if(it!=tn[_av].end())  calc(*it);
        printf("%lld\n",ans);
    }
    return 0;
}