#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;
typedef long long ll;
const int N=2e5+5;
int n,a[N];
struct node{
	int Min,l,r;
	ll sum;
}seg[N<<2];
int query(int p,int l,int r,int L,int x){
	if(l==r){
		return seg[p].Min<=x?l:(n+1);
	}
	int mid=(l+r)>>1;
	if(r<L) return n+1;
	if(seg[p].Min>x) return n+1;
	return min(query(p<<1,l,mid,L,x),query(p<<1|1,mid+1,r,L,x));
}
ll calc(int l,int r,int w){
	return 1ll*(r-l+1)*w;
}
node Query(int p,int l,int r,int L,int R);
node upd(node ls,node rs){
	node res; res.l=ls.l, res.r=rs.r;
	//printf("## l :%d %d %d %lld\n",ls.l,ls.r,ls.Min,ls.sum);
	//printf("## r :%d %d %d %lld\n",rs.l,rs.r,rs.Min,rs.sum);
	res.Min=min(ls.Min,rs.Min);
	if(ls.Min>=a[rs.l]){
		res.sum=ls.sum+rs.sum;
		return res;
	}
	if(ls.Min<rs.Min){
		res.sum=ls.sum+calc(rs.l,rs.r,ls.Min);
		return res;
	}
	int ps=query(1,1,n,rs.l,ls.Min);
	int rsmid=rs.l+rs.r>>1;
	if(ps>rsmid){
		node val=Query(1,1,n,ps,rs.r);
		res.sum=ls.sum+calc(rs.l,ps-1,ls.Min)+val.sum;
	}else{
		node val=Query(1,1,n,rs.l,ps-1);
		res.sum=ls.sum+calc(rs.l,ps-1,ls.Min)-val.sum+rs.sum;
	}
	
	//printf("## s :%d %d %d %lld\n",res.l,res.r,res.Min,res.sum);
	return res;
}
node Query(int p,int l,int r,int L,int R){
	if(L==l&&r==R){
		return seg[p];
	}
	int mid=(l+r)>>1;
	if(R<=mid) return Query(p<<1,l,mid,L,R);
	if(L>mid) return Query(p<<1|1,mid+1,r,L,R);
	node res=upd(Query(p<<1,l,mid,L,mid),Query(p<<1|1,mid+1,r,mid+1,R));
	return res;
}
void upd(int p){
	seg[p]=upd(seg[p<<1],seg[p<<1|1]);
}
void build(int p,int l,int r){
	if(l==r){
		seg[p].Min=a[l];
		seg[p].sum=a[l];
		seg[p].l=l; seg[p].r=r;
		return ;
	}
	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 x){
	if(l==r){
		seg[p].Min=a[l];
		seg[p].sum=a[l];
		return ;
	}
	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);
	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);
		if(opt==1){
			a[p+1]++;
			modify(1,1,n,p+1);
		}else{
			a[p+1]--;
			modify(1,1,n,p+1);
		}
		printf("%lld\n",seg[1].sum);
	}
	return 0;
}
/*
6
6 5 4 7 3 1
0
*/