首先允许离线，一眼莫队……
然后考虑对于每次移动，这不就是让你求逆序对嘛（QAQ）
考虑怎么移动？
- 每次在最后添加一个数，比这个数大的数都会与其形成一个逆序对
- 每次在最后移除一个数，比这个数大的数都会与其形成一个逆序对
- 每次在最前添加一个数，比这个数小的数都会与其减少一个逆序对
- 每次在最前移除一个数，比这个数小的数都会与其减少一个逆序对
那么每次移动的时候我拿树状数组查询一下就好，注意要离散化。
#include<bits/stdc++.h>
#define N 50005
#define inf 1000000007
using namespace std;
typedef unsigned int uint;
uint ans[N],now;
int n,m,a[N],b[N],rt[N];
int c[*N];
struct Query{int l,r,id;}q[*N];
inline int lowbit(int x){return x&(-x);}
bool operator<(Query x,Query y){
if(rt[x.l]==rt[y.l])return x.r<y.r;
return rt[x.l]<rt[y.l];
}
inline void add(int x,int val){
for(int i=x;i<=n;i+=lowbit(i))c[i]+=val;
}
uint ask(int x){
uint ans=;
for(int i=x;i;i-=lowbit(i))ans+=c[i];
return ans;
}
inline int read(){
int f=,x=;char ch;
do{ch=getchar();if(ch=='-')f=-;}while(ch<''||ch>'');
do{x=x*+ch-'';ch=getchar();}while(ch>=''&&ch<='');
return f*x;
}
int main(){
n=read();int x=(int)sqrt(n);
for(int i=;i<=n;i++)a[i]=read(),b[i]=a[i];
sort(b+,b+n+);
for(int i=;i<=n;i++)a[i]=lower_bound(b+,b+n+,a[i])-b;
m=read();
for(int i=;i<=m;i++)q[i].l=read(),q[i].r=read(),q[i].id=i;
for(int i=;i<=n;i++)rt[i]=(i-)/x+;
sort(q+,q+m+);
int l=,r=;
for(int i=;i<=m;i++){
while(l<q[i].l)add(a[l],-),now-=ask(a[l]-),l++;
while(r>q[i].r)add(a[r],-),now-=r-l-ask(a[r]),r--;
while(l>q[i].l)l--,add(a[l],),now+=ask(a[l]-);
while(r<q[i].r)r++,add(a[r],),now+=r-l+-ask(a[r]);
ans[q[i].id]=now;
}
for(int i=;i<=m;i++)printf("%d\n",ans[i]);
return ;
}