#include<bits/stdc++.h>

#define ll long long
#define mk make_pair
#define fi first
#define se second

using namespace std;

inline int read(){
	int x=0,f=1;char c=getchar();
	for(;(c<'0'||c>'9');c=getchar()){if(c=='-')f=-1;}
	for(;(c>='0'&&c<='9');c=getchar())x=x*10+(c&15);
	return x*f;
}

void cmax(int &x,int v){x=max(x,v);}
void cmin(int &x,int v){x=min(x,v);}

const int N=2e5+5;
int p[N],A[N],n,m;
struct BIT{
	int c[N];
	void clear(){memset(c,0,sizeof(c));}
	int lowbit(int x){return x&(-x);}
	void add(int x,int v){for(int i=x;i<=n;i+=lowbit(i))c[i]+=v;}
	int sum(int x){int res=0;for(int i=x;i;i-=lowbit(i))res+=c[i];return res;}
	int qsum(int l,int r){return sum(r)-sum(l-1);}
}T1,T2,T3,T4,T5,T;
// 1 -> (+1,-1)
// 2 -> (-1,+1)
// 3 -> (0,-1)
// 4 -> (-1,0)
// 5 -> (-1,-1)
struct Node{int s,t,f,ad,id;Node(int S,int T,int F,int AD,int I):s(S),t(T),f(F),ad(AD),id(I){}};
vector<Node>ques[N];
ll ans[N],tA[N],tB[N];
vector<pair<int,int> >qA[N],qB[N];
int ql[N],qr[N];

signed main(void){

#ifndef ONLINE_JUDGE
	freopen("in.in","r",stdin);
#endif

	n=read();
	for(int i=1;i<=n;i++)p[i]=read(),A[i]=T.sum(p[i]),T.add(p[i],1);
	// cout<<"A = ";for(int i=1;i<=n;i++)cout<<A[i]<<" ";puts("");
	ll now=0;
	for(int i=1;i<=n;i++)now+=min(A[i],p[i]-1-A[i]);
	// cout<<"now = "<<now<<endl;
	m=read();
	for(int i=1;i<=m;i++){
		int l=read(),r=read();ans[i]=now;ql[i]=l,qr[i]=r;
		if(l==r)continue;
		if(l>r)swap(l,r),swap(ql[i],qr[i]);
		int s=p[l],t=p[r];
		if(s>t){
			ques[r-1].emplace_back(Node(t+1,s-1,1,1,i));
			ques[l].emplace_back(Node(t+1,s-1,-1,1,i));
		}
		else{
			ques[r-1].emplace_back(Node(s+1,t-1,1,-1,i));
			ques[l].emplace_back(Node(s+1,t-1,-1,-1,i));
		}
		qA[r-1].emplace_back(mk(p[l]-1,i));
		qB[l-1].emplace_back(mk(p[r]-1,i));
		if(p[l]>p[r])tA[i]++;
		ans[i]-=min(A[l],p[l]-1-A[l]);
		ans[i]-=min(A[r],p[r]-1-A[r]);
	}

	T.clear();
	for(int i=1;i<=n;i++){
		T.add(p[i],1);
		// cout<<"i = "<<i<<endl;
		if(p[i]%2==0){
			if(A[i]<=(p[i]-4)/2)T1.add(p[i],1);
			else if(A[i]>=(p[i]+2)/2)T2.add(p[i],1);
			else if(A[i]==(p[i]-2)/2)T3.add(p[i],1);
			else if(A[i]==p[i]/2)T4.add(p[i],1);
		}
		else{
			if(A[i]<=(p[i]-3)/2)T1.add(p[i],1);
			else if(A[i]>=(p[i]+1)/2)T2.add(p[i],1);
			else if(A[i]==(p[i]-1)/2)T5.add(p[i],1);
		}
		for(auto [s,t,f,ad,id]:ques[i]){
			// cout<<"Q : "<<s<<" "<<t<<" "<<f<<" "<<ad<<" "<<id<<endl;
			if(ad==1){
				if(f==1)ans[id]+=T1.qsum(s,t)-T2.qsum(s,t)-T4.qsum(s,t)-T5.qsum(s,t);
				else ans[id]-=T1.qsum(s,t)-T2.qsum(s,t)-T4.qsum(s,t)-T5.qsum(s,t);
			}
			else{
				if(f==1)ans[id]+=T2.qsum(s,t)-T1.qsum(s,t)-T3.qsum(s,t)-T5.qsum(s,t);
				else ans[id]-=T2.qsum(s,t)-T1.qsum(s,t)-T3.qsum(s,t)-T5.qsum(s,t);
			}
		}
		// cout<<"now ans = "<<ans[1]<<endl;
		for(auto [lim,id]:qA[i])tA[id]+=T.sum(lim);
		for(auto [lim,id]:qB[i])tB[id]+=T.sum(lim);
	}

	for(int i=1;i<=m;i++){
		if(ql[i]==qr[i]){cout<<now<<'\n';continue;}
		int l=ql[i],r=qr[i];
		cout<<ans[i]+min(tA[i],p[l]-1-tA[i])+min(tB[i],p[r]-1-tB[i])<<'\n';
	}

	return 0;
}