#include<bits/stdc++.h> #define MAXN 50005 usingnamespace std; inlineintread(){ int x=0,f=1; char ch=getchar(); while (ch<'0'||ch>'9'){ if (ch=='-') f=-1; ch=getchar(); } while (ch>='0'&&ch<='9'){ x=(x<<3)+(x<<1)+(ch^'0'); ch=getchar(); } return x*f; } int a[MAXN],b[MAXN],n; namespace BIT{ int c[MAXN]; #define lowbit(x) (x&-x) inlinevoidUpdate(int pos,int val){ for (registerint i=pos;i<MAXN;i+=lowbit(i)){ c[i]+=val; } } inlineintGetSmaller(int pos){ pos--; int ans=0; for (registerint i=pos;i>0;i-=lowbit(i)){ ans+=c[i]; } return ans; } inlineintGetBigger(int num){ returnGetSmaller(MAXN-1)-GetSmaller(num+1); } } usingnamespace BIT; inlinevoiddiscrete(){ for (registerint i=1;i<=n;++i){ b[i]=a[i]; } sort(b+1,b+1+n); for (registerint i=1;i<=n;++i){ a[i]=lower_bound(b+1,b+1+n,a[i])-b; } }
int pos[MAXN]; structQuery{ int l,r,id; }q[MAXN]; inlinebooloperator < (const Query &a,const Query &b){ return pos[a.l]<pos[b.l]||(pos[a.l]==pos[b.l]&&((pos[a.l]&1)?a.r<b.r:a.r>b.r)); } int Ans[MAXN]; intmain(){ n=read(); int Size=sqrt(n); for (registerint i=1;i<=n;++i){ a[i]=read(); pos[i]=(i-1)/Size+1; } discrete(); int m=read(); for (registerint i=1;i<=m;++i){ q[i].l=read(),q[i].r=read(),q[i].id=i; } sort(q+1,q+1+m); int l=1,r=0,ans=0; for (registerint i=1;i<=m;++i){ while (l<q[i].l){ Update(a[l],-1); ans-=GetSmaller(a[l++]); } while (l>q[i].l){ Update(a[--l],1); ans+=GetSmaller(a[l]); } while (r<q[i].r){ Update(a[++r],1); ans+=GetBigger(a[r]); } while (r>q[i].r){ Update(a[r],-1); ans-=GetBigger(a[r--]); } Ans[q[i].id]=ans; } for (registerint i=1;i<=m;++i){ printf("%d\n",Ans[i]); } }