#include <iostream>
#include <cstdio>
#include <cmath>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
const int N=4e5+5;
typedef long long ll;
int n,a[N],b[N];
struct node{
	int Min,l,r,tag;
	ll sum;
}seg[N<<2];
ll calc(int l,int r,int w){
	return 1ll*(r-l+1)*w;
}
void pushdown(int p){
	if(seg[p].tag==-1) return ;
	int ls=p<<1,rs=p<<1|1,&tg=seg[p].tag;
	seg[ls].tag=tg;
	seg[rs].tag=tg;
	seg[ls].sum=calc(seg[ls].l,seg[ls].r,tg);
	seg[rs].sum=calc(seg[rs].l,seg[rs].r,tg);
	tg=-1;
}
void upd(int p){
	seg[p].Min=min(seg[p<<1].Min,seg[p<<1|1].Min);
	seg[p].sum=seg[p<<1].sum+seg[p<<1|1].sum;
}
int queryless(int p,int l,int r,int x){
	if(l==r){
		return seg[p].Min<=x?l:(n+1);
	}
	pushdown(p);
	int mid=(l+r)>>1;
	if(seg[p<<1].Min<=x) return queryless(p<<1,l,mid,x);
	else return queryless(p<<1|1,mid+1,r,x);
}
int querypre(int p,int l,int r,int R){
	if(r<=R){
		return seg[p].Min;
	}
	if(l>R) return n+1;
	pushdown(p);
	int mid=(l+r)>>1;
	return min(querypre(p<<1,l,mid,R),querypre(p<<1|1,mid+1,r,R));
}
void build(int p,int l,int r){
	if(l==r){
		seg[p].tag=-1;
		seg[p].Min=a[l];
		seg[p].sum=b[l];
		seg[p].l=l; seg[p].r=r;
		return ;
	}
	seg[p].l=l; seg[p].r=r;
	seg[p].tag=-1;
	int mid=(l+r)>>1;
	build(p<<1,l,mid),build(p<<1|1,mid+1,r);
	upd(p);
}
void modify(int p,int l,int r,int L,int R,int x){
	if(L==l&&r==R){
		seg[p].tag=x;
		seg[p].sum=calc(l,r,x);
		//printf("$$$ %d %d %d %lld %d\n",p,l,r,seg[p].sum,seg[p].tag);
		return ;
	}
	pushdown(p);
	int mid=(l+r)>>1;
	if(R<=mid) modify(p<<1,l,mid,L,R,x); else
	if(L>mid) modify(p<<1|1,mid+1,r,L,R,x); else
	modify(p<<1,l,mid,L,mid,x),modify(p<<1|1,mid+1,r,mid+1,R,x);
	upd(p);
	//printf("$$$ %d %d %d %lld %d\n",p,l,r,seg[p].sum,seg[p].tag);
}
void Modify(int p,int l,int r,int x){
	if(l==r){
		seg[p].Min=a[x];
		return ;
	}
	pushdown(p);
	int mid=(l+r)>>1;
	if(x<=mid) Modify(p<<1,l,mid,x);
	else Modify(p<<1|1,mid+1,r,x);
	upd(p);
}
int main(){
	scanf("%d",&n);
	rep(i,1,n) scanf("%d",a+i);
	b[1]=a[1];
	rep(i,2,n) b[i]=min(b[i-1],a[i]);
	build(1,1,n);
	printf("%lld\n",seg[1].sum);
	int Q; scanf("%d",&Q);
	while(Q--){
		int opt,p;
		scanf("%d%d",&opt,&p);
		p++;
		//if(n>=100) printf("#%d %d\n",opt,p); 
		if(opt==1){
			a[p]++;
			Modify(1,1,n,p);
			int Min=querypre(1,1,n,p);
			int ps=queryless(1,1,n,Min-1);
			modify(1,1,n,p,ps-1,Min);
		}else{
			a[p]--;
			Modify(1,1,n,p);
			int Min=querypre(1,1,n,p);
			int ps=queryless(1,1,n,Min-1);
			modify(1,1,n,p,ps-1,Min);
			if(n>=100) printf("### %d %d %d\n",p,ps,Min);
			if(n>=100){
				b[1]=a[1];
				rep(i,2,n) b[i]=min(b[i-1],a[i]);
				b[n+1]=-1;
				if(b[ps]>b[p]||b[p]!=Min||b[ps-1]<Min) puts("FUCK");
			}
		}
		printf("%lld\n",seg[1].sum);
	}
	return 0;
}
/*
10
3 8 1 4 10 3 10 9 7 10
8
2 5
1 4
1 2
1 4
1 3
1 3
1 0
2 8



10
4 8 2 6 12 3 10 9 6 10
2
2 5
2 8
*/