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