#include<bits/stdc++.h>
#define ls tree[i].lss
#define rs tree[i].rss
#define int long long
const int N=1e5*2+1000;
const int T=5e6+1000;
using namespace std;
int rt[N],b[N*2],a[N],len,cntl,cntr,L[N],R[N],n,m;
struct ccc{
	int lss,rss,siz,sez;
}tree[T];
int cnt;int tot;
int copy(int old){
	tree[++cnt]=tree[old];
	return cnt;
}
int low_bit(int x){return x&-x;}
int id(int x){return lower_bound(b+1,b+len+1,x)-b;}
int add(int i,int l,int r,int x,int k){
	i=copy(i);
	if(l==r){
		tree[i].siz+=k;
		return i;
	}
	int mid=(l+r)>>1;
	if(x<=mid)ls=add(ls,l,mid,x,k);
	else rs=add(rs,mid+1,r,x,k);
	tree[i].siz=tree[ls].siz+tree[rs].siz;
	return i;
}
void change(int rot,int id,int v){
	while(rot<=n){
		rt[rot]=add(rt[rot],1,len,id,v);
		rot+=low_bit(rot);
	}
}
void pre_get(int x,int y){
	cntl=cntr=0;
	for(int i=x-1;i;i-=low_bit(i))L[++cntl]=rt[i];
	for(int i=y;i;i-=low_bit(i))R[++cntr]=rt[i];
}
int rk(int l,int r,int k,int opt){
	if(l==r){
        int si=0;
        if(!opt)return 0;
        for(int i=1;i<=cntl;i++)si-=tree[tree[L[i]].lss].siz;
    	for(int i=1;i<=cntr;i++)si+=tree[tree[R[i]].lss].siz;
        return opt*(si);
    }
	int si=0;
	for(int i=1;i<=cntl;i++)si-=tree[tree[L[i]].lss].siz;
	for(int i=1;i<=cntr;i++)si+=tree[tree[R[i]].lss].siz;
	int mid=(l+r)>>1;
	if(k<=mid){
		for(int i=1;i<=cntl;i++)L[i]=tree[L[i]].lss;
		for(int i=1;i<=cntr;i++)R[i]=tree[R[i]].lss;
		return rk(l,mid,k,opt);
	}
	else{
		for(int i=1;i<=cntl;i++)L[i]=tree[L[i]].rss;
		for(int i=1;i<=cntr;i++)R[i]=tree[R[i]].rss;
		return rk(mid+1,r,k,opt)+si;
	}
}
int get_rnk(int x,int y,int k,int opt){pre_get(x,y);return rk(1,len,k,opt);}
void replace(int pos,int x,int y){change(pos,id(x),-1);change(pos,id(y),1);}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		b[i]=a[i];
	}
	sort(b+1,b+n+1);
	len=unique(b+1,b+n+1)-b-1;
	for(int i=1;i<=n;i++){change(i,id(a[i]),1);}
	int ans=0;
	for(int i=1;i<=n;i++){ans+=get_rnk(i,n,id(a[i]),0);}
	cout<<ans<<"\n";
	cin>>m;
	for(int i=1;i<=m;i++){
        int x,y;
        cin>>x>>y;
        if(x>y)swap(x,y);
//        if(a[x]==a[y]){
//			cout<<ans<<'\n';
//			continue;
//		}
        int ax=a[x],ay=a[y];
        int num=y-x+1;
        int oldx=get_rnk(x,y,id(a[x]),0),oldy=num-get_rnk(x,y,id(a[y]),1);
        if(a[y]<a[x])ans++;else if(a[x]<a[y]) ans--;
        replace(x,a[x],ay),replace(y,a[y],ax);
        swap(a[x],a[y]);
        int ansx=get_rnk(x,y,id(a[x]),0),ansy=num-get_rnk(x,y,id(a[y]),1);
        ans=ans+ansx+ansy-oldx-oldy;
        cout<<ans<<'\n';
    }
	return 0;
}