#include<bits/stdc++.h>
using namespace std;
#define int long long 
int n,a[200100];
int mn[1001001],s[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]+(mid+1)*max(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]=a[l],s[p]=0,void();
	int mid=l+r>>1;
	if(x<=mid)push(p<<1,l,mid,x,pre);
	else push(p<<1|1,mid+1,r,x,min(pre,mn[p<<1]));
	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(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<<mn[1]<<" "<<ls[1]<<" "<<s[1]<<"\n";
			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";
		}
	}
}