#include<bits/stdc++.h>
#define mid (l+r>>1)
using namespace std;
long long n,q;
long long sum[800010];
long long add[800010];
void pushdown(long long k,long long l,long long r){
	add[k<<1]+=add[k];
	add[k<<1|1]+=add[k];
	sum[k<<1]+=add[k]*(mid-l+1);
	sum[k<<1|1]+=add[k]*(r-mid);
	add[k]=0;
}
void update(long long k,long long l,long long r,long long x,long long y,long long v){
	if(l>y||r<x){
		return;
	}
	if(l>=x&&r<=y){
		sum[k]+=v*(r-l+1);
		add[k]+=v;
		return;
	}
	pushdown(k,l,r);
	update(k<<1,l,mid,x,y,v);
	update(k<<1|1,mid+1,r,x,y,v);
	sum[k]=sum[k<<1]+sum[k<<1|1];
}
long long query(long long k,long long l,long long r,long long x,long long y){
	if(l>y||r<x){
		return 0;
	}
	pushdown(k,l,r);
	if(l>=x&&r<=y){
		return sum[k];
	}
	return query(k<<1,l,mid,x,y)+query(k<<1|1,mid+1,r,x,y);
}
long long ans;
int main(){
	cin>>n;
	for(long long i=1;i<=n;i++){
		long long u;
		cin>>u;
		ans+=u;
		update(1,1,n,u,u,1);
	}
	cin>>q;
	while(q--){
		long long u,v;
		cin>>u>>v;
		long long num=query(1,1,n,u,u);
		ans+=num*(v-u);
		update(1,1,n,u,u,-num);
		update(1,1,n,v,v,num);
		cout<<ans<<'\n';
	}
	return 0;
}