#include<bits/stdc++.h>
using namespace std;
#define int long long 
int n,a[200100];
int mn[1001001],s[1001001],ls[1001001];
int ss[1001001],sss[1001001];
void build(int p,int l,int r,int pre){
	if(l==r)return mn[p]=a[l],ls[p]=min(pre,a[l]),s[p]=0,void();
	int mid=l+r>>1;
	build(p<<1,l,mid,pre);build(p<<1|1,mid+1,r,min(mn[p<<1],pre));
	mn[p]=min(mn[p<<1],mn[p<<1|1]);
	ls[p]=ls[p<<1];
	s[p]=s[p<<1]+s[p<<1|1]+(mid+1)*max(min(pre,mn[p<<1])-ls[p<<1|1],0ll);
}
void push(int p,int l,int r,int x,int pre){
	if(l==r)return mn[p]=a[l],ls[p]=min(pre,a[l]),s[p]=0,void();
	int mid=l+r>>1;
//	if(x==1)cout<<l<<" "<<r<<" "<<x<<" "<<pre<<"\n";
	if(x>=l){
		if(x<=mid)push(p<<1,l,mid,x,pre);
		push(p<<1|1,mid+1,r,x,min(pre,mn[p<<1]));
	}else{
		if(pre<=mn[p<<1])ls[p<<1]=pre,s[p<<1]=0,push(p<<1|1,mid+1,r,x,pre);
		else push(p<<1,l,mid,x,pre);
	}
	mn[p]=min(mn[p<<1],mn[p<<1|1]);
	ls[p]=ls[p<<1];
	s[p]=s[p<<1]+s[p<<1|1]+(mid+1)*max(min(pre,mn[p<<1])-ls[p<<1|1],0ll);
}
signed main(){
	cin>>n;
	for (int i=0;i<n;i++)
	cin>>a[i];
	int q;
	cin>>q;
	build(1,0,n-1,1e9);
	cout<<s[1]+mn[1]*n<<"\n";
	int op,x;
	while(q--){
		cin>>op;
		if(op==1){
			cin>>x;
			a[x]++;
			push(1,0,n-1,x,1e9);
			cout<<s[1]+mn[1]*n<<"\n";
		}else {
			cin>>x;
			a[x]--;
			push(1,0,n-1,x,1e9);
			cout<<s[1]+mn[1]*n<<"\n";
		}
	}
}