#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

int read()

{

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

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

    while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();

    return x*f;

}

#define N 50010

int n,a[N],b[N],tree[N],m,block;

long long ans[N];

struct data

{

    int i,k,l,r;

    bool operator <(const data&a) const

    {

        return k<a.k||k==a.k&&((k&)?r<a.r:r>a.r);

    }

}q[N];

void add(int k,int x){while (k<=n) tree[k]+=x,k+=k&-k;}

int query(int k){int s=;while (k) s+=tree[k],k-=k&-k;return s;}

int main()

{

#ifndef ONLINE_JUDGE

    freopen("bzoj3289.in","r",stdin);

    freopen("bzoj3289.out","w",stdout);

    const char LL[]="%I64d\n";

#else

    const char LL[]="%lld\n";

#endif

    n=read();

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

    sort(b+,b+n+);

    int t=unique(b+,b+n+)-b;

    for (int i=;i<=n;i++) a[i]=lower_bound(b+,b+t,a[i])-b;

    m=read();

    block=sqrt(n);

    for (int i=;i<=m;i++) q[i].i=i,q[i].l=read(),q[i].r=read(),q[i].k=q[i].l/block;

    sort(q+,q+m+);

    q[].l=;

    for (int i=;i<=m;i++)

    {

        ans[q[i].i]=ans[q[i-].i];

        while (q[i-].r<q[i].r) ans[q[i].i]+=query(n)-query(a[++q[i-].r]),add(a[q[i-].r],);

        while (q[i-].r>q[i].r) add(a[q[i-].r],-),ans[q[i].i]-=query(n)-query(a[q[i-].r--]);

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

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

    }

    for (int i=;i<=m;i++) printf(LL,ans[i]);

    return ;

}