1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<algorithm>
5 #include<cmath>
6 using namespace std;
7 #define N 50010
8 #define lowbit(x) x&-x
9 struct Node{
10 int l,r,f;
11 }a[N];
12 struct Ls{
13 int w,f;
14 }l[N];
15 int Ans[N],s,i,j,k,n,m,b[N],c[N],A[N],q,L,R,Res,Sum;
16 inline bool Cmp1(Ls a,Ls b){return a.w<b.w;}
17 inline bool Cmp2(Node x,Node y){
18 if(b[x.l]==b[y.l])return x.r<y.r;
19 return b[x.l]<b[y.l];
20 }
21 inline int Query(int x){
22 int Ans=0;
23 for(;x;x-=lowbit(x))Ans+=c[x];
24 return Ans;
25 }
26 inline void Update(int x,int y){for(;x<=m;x+=lowbit(x))c[x]+=y;}
27 int main(){
28 scanf("%d",&n);
29 for(i=1;i<=n;i++)scanf("%d",&l[i].w),l[i].f=i;
30 sort(l+1,l+n+1,Cmp1);
31 A[l[1].f]=m=1;
32 for(i=2;i<=n;i++)
33 if(l[i].w==l[i-1].w)A[l[i].f]=m;else A[l[i].f]=++m;
34 s=sqrt((double)n);
35 for(i=1;i<=n;i++)b[i]=(i-1)/s+1;
36 scanf("%d",&q);
37 for(i=1;i<=q;i++)scanf("%d%d",&a[i].l,&a[i].r),a[i].f=i;
38 sort(a+1,a+q+1,Cmp2);
39 for(i=L=1;i<=q;i++){
40 while(a[i].l<L)L--,Res+=Query(A[L]-1),Update(A[L],1);
41 while(a[i].r>R)R++,Update(A[R],1),Res+=R-L+1-Query(A[R]);
42 while(a[i].l>L)Res-=Query(A[L]-1),Update(A[L],-1),L++;
43 while(a[i].r<R)Update(A[R],-1),Res-=R-L-Query(A[R]),R--;
44 Ans[a[i].f]=Res;
45 }
46 for(i=1;i<=q;i++)printf("%d\n",Ans[i]);
47 return 0;
48 }
