#include<iostream>
#include<algorithm>
#include<cmath>
#define int long long
using namespace std;
const int N=2e6+10;
const int M=1e3+10;
int n,m;
int tree[N];
inline int lowbit(int x){return x&-x;}
inline void updata(int x)
{
	while(x<=n){++tree[x],x+=lowbit(x);}
	return;
}
inline int query(int x)
{
	int sum=0;
	while(x){sum+=tree[x],x-=lowbit(x);}
	return sum;
}
int ans=0;
int a[N],b[N];
int st[M],ed[M],pos[N];
inline int change(int l,int r)
{
	int w=1;
	int mi=min(a[l],a[r]);
	int ma=max(a[l],a[r]);
	if(a[l]>a[r]) w=-1;
	swap(a[l],a[r]);
	for(int i=st[pos[l]];i<=ed[pos[l]];i++) b[i]=a[i];
	sort(b+st[pos[l]],b+ed[pos[l]]+1);
	for(int i=st[pos[r]];i<=ed[pos[r]];i++) b[i]=a[i];
	sort(b+st[pos[r]],b+ed[pos[r]]+1);
	int res=0;
	if(pos[l]==pos[r])
		for(int i=l+1;i<=r-1;i++) res+=(a[i]>mi&&a[i]<ma);
	else{
		for(int i=pos[l]+1;i<=pos[r]-1;i++)
			res+=upper_bound(b+st[i],b+ed[i]+1,ma)-lower_bound(b+st[i],b+ed[i]+1,mi);
		for(int i=l+1;i<=ed[pos[l]];i++) res+=(a[i]>mi&&a[i]<ma);
		for(int i=st[pos[r]];i<=r-1;i++) res+=(a[i]>mi&&a[i]<ma);
	}
	return (2*res+1)*w;
}
inline void build(int n)
{
	int len=sqrt(n);
	int t=n/len+(bool)(n%len);
	for(int i=1;i<=n;i++)
		pos[i]=(i-1)/len+1,b[i]=a[i];
	for(int i=1;i<=t;i++)
	{
		st[i]=(i-1)*len+1,ed[i]=(i==t)?n:i*len;
		sort(b+st[i],b+ed[i]+1);
	}
	return;
}
inline void init()
{
	sort(b+1,b+1+n);
	for(int i=1;i<=n;i++) a[i]=lower_bound(b+1,b+1+n,a[i])-b;
	for(int i=1;i<=n;i++)
		updata(a[i]),ans+=i-query(a[i]);
	cout<<ans<<'\n';
	return;
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i],b[i]=a[i];
	init();
	build(n);
	cin>>m;
	int l,r;
	while(m--)
	{
		cin>>l>>r;
		if(l>r) swap(l,r);
		ans+=change(l,r);
		cout<<ans<<'\n';
	}
	return 0;
}