只能过样例QWQ

#include"bits/stdc++.h"
#define re register
#define lb(x) (x&(-x))
using namespace std;
const int maxn=1e5+10;
int n,Q,siz;
int a[maxn],b[maxn],tr[maxn],pre[maxn],pre1[maxn],ans[maxn];
struct q1{
	int l,r,id,ans;
}q[maxn];
struct node{
	int l,r,id,op;
};
vector<node> g1[maxn],g2[maxn];
inline void update(int x,int val){while(x<=n) tr[x]+=val,x+=lb(x);}
inline int query(int x){int sum=0;while(x>0) sum+=tr[x],x-=lb(x);return sum;}
inline bool cmp(q1 a,q1 b){return ((a.l/siz)^(b.l/siz))?(a.l/siz)<(b.l/siz):((a.l/siz)&1)?a.r<b.r:a.r>b.r;}
signed main(){
#ifndef ONLINE_JUDGE
	freopen("1.in","r",stdin);
	freopen("1.out","w",stdout);
#endif
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n>>Q;
	for(re int i=1;i<=n;++i) cin>>a[i],b[i]=a[i];
	sort(b+1,b+n+1);
	int len=unique(b+1,b+n+1)-(b+1);
	for(re int i=1;i<=n;++i) a[i]=lower_bound(b+1,b+len+1,a[i])-b;
	for(re int i=1;i<=Q;++i) cin>>q[i].l>>q[i].r,q[i].id=i;
	for(re int i=1;i<=n;++i){
		update(a[i],1);
		pre[i]=query(a[i+1]-1);
		pre1[i]=query(n)-query(a[i+1]);
	}
	siz=sqrt(n);
	sort(q+1,q+Q+1,cmp);
	int l=1,r=0;
	for(re int i=1;i<=Q;++i){
		if(l>q[i].l) g1[r].push_back({q[i].l,l-1,i,1});
		while(l>q[i].l){--l;q[i].ans-=pre[l-1];}
		if(r<q[i].r) g2[l-1].push_back({r+1,q[i].r,i,-1});
		while(r<q[i].r){q[i].ans+=pre1[r];++r;}
		if(l<q[i].l) g1[r].push_back({l,q[i].l-1,i,-1});
		while(l<q[i].l){q[i].ans+=pre[l-1];++l;}
		if(r>q[i].r) g2[l-1].push_back({q[i].r+1,r,i,1});
		while(r>q[i].r){--r;q[i].ans-=pre1[r];}
	}
	for(re int i=1;i<=n;++i) update(a[i],-1);
	for(re int i=1;i<=n;++i){
		update(a[i],1);
		for(auto x:g1[i]){
			for(re int j=x.l,res;j<=x.r;++j){
				res=query(a[j]-1);
				q[x.id].ans+=x.op*res;
			}
		}
		for(auto x:g2[i]){
			for(re int j=x.l,res;j<=x.r;++j){
				res=query(n)-query(a[j]);
				q[x.id].ans+=x.op*res;
			}
		}
	}
	for(re int i=1;i<=Q;++i) q[i].ans+=q[i-1].ans;
	for(re int i=1;i<=Q;++i) ans[q[i].id]=q[i].ans;
	for(re int i=1;i<=Q;++i) cout<<ans[i]<<'\n';
    return 0;
}