#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define int long long
const int N=1e5+5;
const double eps=1e-10;
const int mod=998244353;
#define endl '\n'
struct node{
    int n=0,m=0;
    int cnt=0;
    static const int maxn=1e5+5;
    int c[maxn];
    int lowbit(int x){
        return x&(-x);
    }
    void add(int i,int x){
        while(i<=maxn){
            c[i]+=x;
            i+= lowbit(i);
        }
    }
    int ask(int i){
        int ans=0;
        while(i){
            ans+=c[i];
            i-=lowbit(i);
        }
        return ans;
    }
    struct dian{
      int x,y,id;
      inline bool operator<(const dian &a)const{
          return x<a.x;
      }
    }v[maxn];
    struct que{
        int x,y,k,id;
        inline bool operator<(const que &a)const{
            return x<a.x;
        }
    }que[4*maxn];
    void vadd(int x,int y){
        v[++n].x=x;
        v[n].y=y;
    }
    void vque(int x1,int y1,int x2,int y2,int id){
       que[++cnt]={x1-1,y1-1,1,id};
        que[++cnt]={x1-1,y2,-1,id};
        que[++cnt]={x2,y1-1,-1,id};
        que[++cnt]={x2,y2,1,id};
    }
    void get(int *a){
        sort(v+1,v+1+n);
        sort(que+1,que+1+cnt);
        int l=1;
        for(int i=1;i<=cnt;i++){
            while(l<=n&&v[l].x<=que[i].x){
                add(v[l].y,1);
                l++;
            }
            a[que[i].id]+=que[i].k*ask(que[i].y);
        }
        return;
    }
}t1,t2,t3,t4,t5,t6,t7,tt

;
const int MAXN=2e5+5;
int ans1[MAXN], ans2[MAXN], ans3[MAXN], ans4[MAXN], ans5[MAXN],ans6[MAXN], ans7[MAXN];
void solve(){
    int n;
    cin>>n;
    vector<int>a(n+5),b(n+5),p(n+5);
    int sum=0;
    for(int i=1;i<=n;i++){
        cin>>p[i];
        a[i]=tt.ask(p[i]);
        b[i]=p[i]-a[i]-1;
        tt.add(p[i],1);
        if(a[i]==b[i]){
            t1.vadd(i,p[i]);
        }else if(a[i]==b[i]+1){
            t2.vadd(i,p[i]);
        }else if(a[i]>=b[i]+2){
            t3.vadd(i,p[i]);
        }else if(a[i]+1==b[i]){
            t4.vadd(i,p[i]);
        }else if(a[i]+2<=b[i]){
            t5.vadd(i,p[i]);
        }
        t6.vadd(i,p[i]);
        t7.vadd(i,p[i]);
        sum+=min(a[i],b[i]);
    }
    int m;
    cin>>m;
    vector<int>x1(m+5),x2(m+5);

    for(int i=1;i<=m;i++){
        int l,r;
        cin>>l>>r;
        if(l>r){
            swap(l,r);
        }
        x1[i]=l,x2[i]=r;
        if(l==r)continue;
        int xl=min(p[l],p[r]),yr=max(p[l],p[r]);
        l++,r--;
        t1.vque(l,xl,r,yr,i);
        t2.vque(l,xl,r,yr,i);
        t3.vque(l,xl,r,yr,i);
        t4.vque(l,xl,r,yr,i);
        t5.vque(l,xl,r,yr,i);
        t6.vque(l,1,r+1,p[l-1]-1,i);
        t7.vque(l-1,1,r,p[r+1]-1,i);
    }
    t1.get(ans1);
    t2.get(ans2);
    t3.get(ans3);
    t4.get(ans4);
    t5.get(ans5);
    t6.get(ans6);
    t7.get(ans7);
    for(int i=1;i<=m;i++){
        if(x1[i]==x2[i]){
            cout<<sum<<endl;
        }else{
            int ans=0;
            if(p[x1[i]]<p[x2[i]]){
                ans+=sum-ans1[i]+ans3[i]-ans4[i]-ans5[i];
            }else{
                ans+=sum-ans1[i]-ans2[i]-ans3[i]+ans5[i];
            }
            ans+=(min(a[x1[i]]+ans6[i],b[x1[i]]-ans6[i]))-min(a[x1[i]],b[x1[i]]);
            ans+=(min(a[x2[i]]-ans7[i],b[x2[i]]+ans7[i]))-min(a[x2[i]],b[x2[i]]);
            cout<<ans<<endl;
        }
    }
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    //cout<<fixed<<setprecision(12);
    int T=1;
   // cin>>T;
    while(T--) solve();
    return 0;
}