#include <bits/stdc++.h>
#define int long long
using namespace std;
int a[100005],A[100005],B[100005],C[100005];
struct BIT
{
	int tree[100005];
	inline void cl()
	{
		memset(tree,0,sizeof tree);
	}
	inline int lowbit(int x)
	{
		return x&-x;
	}
	inline void add(int x,int y)
	{
		if(x>100000) return ;
		tree[x]+=y,add(x+lowbit(x),y);
	}
	inline int ask(int x)
	{
		if(!x) return 0;
		return tree[x]+ask(x^lowbit(x));
	}
}T[6];
int out[200005],n,q,ans;
struct query
{
	int op,t,x,w,id;
}b[6000005];
int cnt=0;
inline void ins(int op,int l,int r,int L,int R,int w,int id)
{
	b[++cnt]={op,r,R,w,id};
	b[++cnt]={op,l-1,R,-w,id};
	b[++cnt]={op,r,L-1,-w,id};
	b[++cnt]={op,l-1,L-1,w,id};
}
inline bool cmp(query x,query y)
{
	return x.t<y.t;
}
inline void solve()
{
	sort(b+1,b+cnt+1,cmp);
	int nw=0;
	for(int i=1;i<=cnt;i++)
	{
		while(nw<b[i].t)
		{
			++nw;
			if(A[nw]>B[nw]+1) T[0].add(a[nw],1);
			if(B[nw]>A[nw]+1) T[1].add(a[nw],1);
			if(A[nw]==B[nw]+1) T[2].add(a[nw],1);
			if(B[nw]==A[nw]+1) T[3].add(a[nw],1);
			if(A[nw]==B[nw]) T[4].add(a[nw],1);
			T[5].add(a[nw],1);
		}
		if(b[i].op!=-1) out[b[i].id]+=T[b[i].op].ask(b[i].x)*b[i].w;
		else
		{
			int A=T[5].ask(b[i].x-1)+b[i].w;
			int B=b[i].x-A-1;
			out[b[i].id]+=min(A,B);
	//		cout << b[i].x << " " << b[i].t << " " << A << " " << B << "\n";
		}
	}
	for(int i=1;i<=q;i++)
		cout << out[i]+ans << "\n"; 
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n;
	for(int i=1;i<=n;i++)
		cin >> a[i];
	for(int i=1;i<=n;i++)
	{
		A[i]=T[0].ask(a[i]);
		T[0].add(a[i],1);
	}
	T[0].cl();
	for(int i=n;i>=1;i--)
	{
		B[i]=T[0].ask(a[i]);
		T[0].add(a[i],1);
	}
	for(int i=1;i<=n;i++)
		ans+=C[i]=min(A[i],B[i]);
	T[0].cl();
	cin >> q;
	for(int i=1;i<=q;i++)
	{
		int x,y,id=i;
		cin >> x >> y;
		if(x>y) swap(x,y);
		if(x==y)
		{
			out[i]=0;
			continue;
		}
		out[i]-=C[x],out[i]-=C[y];
		if(a[x]<a[y])
		{
			int l=x+1,r=y-1,L=a[x]+1,R=a[y]-1;
			ins(0,l,r,L,R,1,id);
			ins(1,l,r,L,R,-1,id);
			ins(3,l,r,L,R,-1,id);
			ins(4,l,r,L,R,-1,id);
			b[++cnt]={-1,y-1,a[x],0,i};
			b[++cnt]={-1,x-1,a[y],0,i};
		}
		else
		{
			int l=x+1,r=y-1,L=a[y]+1,R=a[x]-1;
			ins(0,l,r,L,R,-1,id);
			ins(1,l,r,L,R,1,id);
			ins(2,l,r,L,R,-1,id);
			ins(4,l,r,L,R,-1,id);
			b[++cnt]={-1,y-1,a[x],1,i};
			b[++cnt]={-1,x-1,a[y],0,i};
		}
	}
	solve();
	return 0;
}