#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#define I inline
#define nnq nanachi
using namespace std;

const int N = 20010;
const int S = 500;
struct St {
	int num,val;
}mk[N];
int cnt[S][N],sum[S][S];
int n,m,org,rt,vtot,h[N],nl[S],nr[S],ml[S],mr[S],mbel[N],nbel[N];

I bool cmp(St s1,St s2) {
	return s1.val<s2.val;
}
I void build() {
	int t=sqrt(n),tm=sqrt(vtot); 
	for(int i=1;i<=tm;++i) {
		ml[i]=(i-1)*tm+1; mr[i]=i*tm;
		for(int j=ml[i];j<=mr[i];++j) mbel[j]=i;
	}
	if(mr[tm]<vtot) {
		tm++; ml[tm]=mr[tm-1]+1; mr[tm]=vtot;
		for(int j=ml[tm];j<=mr[tm];++j) mbel[j]=tm;
	}
	for(int i=1;i<=t;++i) {
		nl[i]=(i-1)*t+1; nr[i]=i*t;
		memcpy(cnt[i],cnt[i-1],sizeof(cnt[i]));
		memcpy(sum[i],sum[i-1],sizeof(sum[i]));
		for(int j=nl[i];j<=nr[i];++j) {
			nbel[j]=i;	
			cnt[i][h[j]]++;
			sum[i][mbel[h[j]]]++;
		}
	}
	if(nr[t]<n) {
		t++; nl[t]=nr[t-1]+1; nr[t]=n;
		memcpy(cnt[t],cnt[t-1],sizeof(cnt[t]));
		for(int j=nl[t];j<=nr[t];++j) {
			nbel[j]=t;	
			cnt[t][h[j]]++;
			sum[t][mbel[h[j]]]++;
		}
	}
	rt=t;
}
int nnq[N];
I int lowbit(int x) { return x&(-x); }
I int add(int x,int val) { while(x<=vtot) {nnq[x]+=val,x+=lowbit(x);} };
I int ask(int x) { 
	int ret=0;
	while(x) {
		ret+=nnq[x];
		x-=lowbit(x);
	}
	return ret;
}
I void getorg() {
	for(int i=1;i<=n;++i) {
		add(h[i],1);
		org+=i-ask(h[i]);	
	}
}
I int qplus(int l,int r) {
	int vmax=max(h[l],h[r]),vmin=min(h[l],h[r]);
	if(vmax==vmin) return 0;
	if(nbel[r]-nbel[l]<=1) {
		int ret=0;
		for(int i=l+1;i<=r-1;++i) {
			if(h[i]>=vmin&&h[i]<=vmax) ret+=2;
			if(h[i]==vmin||h[i]==vmax) ret--;
		}
		return (h[l]<h[r]?1:-1)*(ret+1); 
	}
	int ret=0;
	for(int i=l+1;i<=nr[nbel[l]];++i) {
		if(h[i]>=vmin&&h[i]<=vmax) ret+=2;
		if(h[i]==vmin||h[i]==vmax) ret--;
	}
	for(int i=r-1;i>=nl[nbel[r]];--i) {
		if(h[i]>=vmin&&h[i]<=vmax) ret+=2;
		if(h[i]==vmin||h[i]==vmax) ret--;
	}
	if(mbel[vmax]-mbel[vmin]<=1) {
		for(int i=vmin+1;i<=vmax-1;++i) ret+=(cnt[nbel[r]-1][i]-cnt[nbel[l]][i])<<1;
		ret+=cnt[nbel[r]-1][vmin]-cnt[nbel[l]][vmin];
		ret+=cnt[nbel[r]-1][vmax]-cnt[nbel[l]][vmax];
		return (h[l]<h[r]?1:-1)*(ret+1);
	}
	for(int i=vmin+1;i<=mr[mbel[vmin]];++i) ret+=(cnt[nbel[r]-1][i]-cnt[nbel[l]][i])<<1;
	for(int i=vmax-1;i>=ml[mbel[vmax]];--i) ret+=(cnt[nbel[r]-1][i]-cnt[nbel[l]][i])<<1;
	ret+=cnt[nbel[r]-1][vmin]-cnt[nbel[l]][vmin];
	ret+=cnt[nbel[r]-1][vmax]-cnt[nbel[l]][vmax];
	for(int i=mbel[vmin]+1;i<=mbel[vmax]-1;++i) ret+=(sum[nbel[r]-1][i]-sum[nbel[l]][i])<<1;
	return (h[l]<h[r]?1:-1)*(ret+1);
}
I void update(int l,int r) {
	for(int i=nbel[l];i<=rt;++i) {
		cnt[i][h[l]]--;
		sum[i][mbel[h[l]]]--;
		cnt[i][h[r]]++;
		sum[i][mbel[h[r]]]++;		
	}
	for(int i=nbel[r];i<=rt;++i) {
		cnt[i][h[r]]--;
		sum[i][mbel[h[r]]]--;	
		cnt[i][h[l]]++;
		sum[i][mbel[h[l]]]++;		
	}
}
I int read() {
	int ret=0; char ch;
	while((ch=getchar())>'9'||ch<'0'); ret=ch-'0';
	while((ch=getchar())>='0'&&ch<='9') ret=ret*10+ch-'0';
	return ret;
}
int main()
{
	n=read();
	for(int i=1;i<=n;++i) h[i]=read(),mk[i].val=h[i],mk[i].num=i;
	sort(mk+1,mk+1+n,cmp); mk[0].val=-114514;
	for(int i=1;i<=n;++i) {
		if(mk[i].val!=mk[i-1].val) vtot++;
		h[mk[i].num]=vtot;
	} 
	build(); getorg();
	cout<<org<<endl;
	m=read();
	for(int i=1;i<=m;++i) {
		int l,r; l=read(); r=read(); if(r<l) swap(l,r);
		printf("%d\n",org=org+qplus(l,r));
		update(l,r); swap(h[l],h[r]); 
	}
	return 0;
}