Mato同学从各路神犇以各种方式（你们懂的）收集了许多资料，这些资料一共有n份，每份有一个大小和一个编号。为了防止他人偷拷，这些资料都是加密过的，只能用Mato自己写的程序才能访问。Mato每天随机选一个区间[l,r]，他今天就看编号在此区间内的这些资料。Mato有一个习惯，他总是从文件大小从小到大看资料。他先把要看的文件按编号顺序依次拷贝出来，再用他写的排序程序给文件大小排序。排序程序可以在1单位时间内交换2个相邻的文件（因为加密需要，不能随机访问）。Mato想要使文件交换次数最小，你能告诉他每天需要交换多少次吗？

//

//  main.cpp

//  分块1

//

//  Created by Candy on 2016/12/17.

//  Copyright © 2016年 Candy. All rights reserved.

//

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

using namespace std;

typedef long long ll;

const int N=5e4+;

inline int read(){

    char c=getchar();int x=,f=;

    while(c<''||c>''){if(c=='-')f=-; c=getchar();}

    while(c>=''&&c<=''){x=x*+c-''; c=getchar();}

    return x*f;

}

int n,Q,a[N],bl,pos[N],mp[N],m;

inline int Bin(int v){

    int l=,r=m;

    while(l<=r){

        int mid=(l+r)>>;

        if(mp[mid]==v) return mid;

        if(v<mp[mid]) r=mid-;

        else l=mid+;

    }

    return -;

}

struct ques{

    int l,r,id;

    bool operator <(const ques a)const{

        if(pos[l]==pos[a.l]) return r<a.r;

        else return pos[l]<pos[a.l];

    }

}q[N];

int c[N];

ll ans,an[N];

inline int lowbit(int x){return x&-x;}

inline void add(int p,int v){for(int i=p;i<=n;i+=lowbit(i))c[i]+=v;}

inline int sum(int p){

    int res=;

    for(int i=p;i;i-=lowbit(i)) res+=c[i];

    return res;

}

inline int sum(int l,int r){

    return sum(r)-sum(l-);

}

void solve(){

    int l=,r=;

    for(int i=;i<=Q;i++){

        while(r<q[i].r) r++,ans+=sum(a[r]+,m),add(a[r],);

        while(r>q[i].r) ans-=sum(a[r]+,m),add(a[r],-),r--;

        while(l<q[i].l) ans-=sum(,a[l]-),add(a[l],-),l++;

        while(l>q[i].l) l--,ans+=sum(,a[l]-),add(a[l],);

        an[q[i].id]=ans;

    }

}

int main(int argc, const char * argv[]) {

    n=read();

    bl=sqrt(n);

    for(int i=;i<=n;i++) a[i]=mp[i]=read(),pos[i]=(i-)/bl+;

    sort(mp+,mp++n);

    m=;

    for(int i=;i<=n;i++) if(a[i]!=a[i-]) a[++m]=a[i];

    for(int i=;i<=n;i++) a[i]=Bin(a[i]);

    Q=read();

    for(int i=;i<=Q;i++) q[i].l=read(),q[i].r=read(),q[i].id=i;

    sort(q+,q++Q);

    solve();

    for(int i=;i<=Q;i++) printf("%lld\n",an[i]);

    return ;

}