1 #include <bits/stdc++.h>
2 #define lowbit(x) x&(-x)
3 #define nmax 50005
4
5 using namespace std;
6 typedef long long ll;
7 int n,q,bn; //bn为每块的大小
8 int data[nmax],c[nmax]={0},lsh[nmax];
9 ll ans[nmax]={0};
10 struct seg{
11 int l,r,pl,id;
12 bool operator < (const seg a) const{ return (a.pl==pl)?(a.r>r):(a.pl>pl); }
13 }qes[nmax];
14
15 void upd(int x,int y){ //y决定是加是减
16 while(x<=n) { c[x]+=y; x+=lowbit(x); }
17 }
18
19 int myfind(int x){
20 int ans=0;
21 while(x>0) { ans+=c[x]; x-=lowbit(x); }
22 return ans;
23 }
24
25 bool mycmp(int a,int b){ return data[a]<data[b]; }
26
27 int main(){
28 cin>>n;
29 bn=sqrt(n);
30 for (int i=1; i<=n; i++) { scanf("%d",&data[i]); lsh[i]=i; }
31 sort(lsh+1,lsh+n+1,mycmp);
32 for (int i=1; i<=n; i++) data[ lsh[i] ]=i;
33 cin>>q;
34 for (int i=1; i<=q; i++) {
35 scanf("%d%d",&qes[i].l,&qes[i].r);
36 qes[i].id=i;
37 qes[i].pl=(qes[i].l-1)/bn+1;
38 }
39 sort(qes+1,qes+q+1);
40 int l=qes[1].l,r=qes[1].l-1,nowl=0,ta=0; //nowl现在该区间的长度
41 for (int i=1; i<=q; i++) {
42 while(qes[i].l<l) l--,upd(data[l],1),ta+=( myfind(data[l])-1 ),nowl++;
43 while(qes[i].r>r) nowl++,r++,upd(data[r],1),ta+=( nowl-myfind(data[r]) );
44 while(qes[i].l>l) ta-=( myfind(data[l])-1 ),upd(data[l],-1),nowl--,l++;
45 while(qes[i].r<r) ta-=( nowl-myfind(data[r]) ),upd(data[r],-1),nowl--,r--;
46 ans[ qes[i].id ]=ta;
47 }
48 for (int i=1; i<=q; i++) printf("%lld
",ans[i]);
49 return 0;
50 }