rt，样例能过，提交全 WA，以后再也不写二次离线莫队了/kel

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+2,M=320;
int belong[N],L[M],R[M];
int n,m,a[N],cnt[N],tag[M];
ll f[N],g[N],ans[N];
vector<int> num;
int sz,blocks;

int read() {
	int x=0; char ch=0; while (!isdigit(ch) ) ch=getchar();
	while (isdigit(ch) ) x=(x<<3)+(x<<1)+(ch&15),ch=getchar();
	return x;
}
struct Query
{
	int l,r,id; ll ans;
	bool operator <(Query o)const {
		return belong[l]^belong[o.l]?l<o.l:r<o.r;
	}
}Q[N];

struct qwq {
	int l,r,id,sign;
};
vector<qwq> qa[N],qb[N];

namespace BIT
{
	int T[N];
	#define lowbit(x) x&-x
	void clear() { memset(T,0,sizeof T); }
	void add(int x) { while (x<=n) T[x]++,x+=lowbit(x); }
	int query(int x,int sum=0) { while (x) sum+=T[x],x-=lowbit(x); return sum; }
}
int Hash(int x) {
	return lower_bound(num.begin(),num.end(),x)-num.begin()+1;
}
void init()
{
	sz=sqrt(n);
	for (int i=1;i<=n;i++) belong[i]=(i-1)/sz;
	for (int i=1;i<=n;i++) num.push_back(a[i]);
	for (int i=1;i<=n;i++) a[i]=Hash(a[i]); sort(Q,Q+m);
	for (int i=1;i<=n;i++) f[i]=f[i-1]+i-1-BIT::query(a[i]),BIT::add(a[i]);
	BIT::clear(); for (int i=n;i>=1;i--) g[i]=g[i+1]+BIT::query(a[i]-1),BIT::add(a[i]);
}
int main()
{
	n=read(),m=read();
	for (int i=1;i<=n;i++) a[i]=read();
	for (int i=0;i<m;i++) Q[i]={read(),read(),i,0};
	init();
	
	for (int i=0,l=1,r=0;i<m;i++)
	{
		int L=Q[i].l,R=Q[i].r;
		Q[i].ans=f[R]-f[r]+g[L]-g[l];
		if (r<R) qa[l].push_back({r+1,R,i,-1});
		if (r>R) qa[l].push_back({R+1,r,i,1});
		if (l>L) qb[R].push_back({L,l-1,i,-1});
		if (l<L) qb[R].push_back({l,L-1,i,1});
		l=L,r=R;
	}
	int nums=num.size(); sz=sqrt(nums),blocks=nums/sz+1;
	for (int i=1;i<=blocks;i++) L[i]=R[i-1]+1,R[i]=i*sz-1;
	R[blocks]=nums;
	
	for (int i=1;i<=n;i++)
	{
		for (auto t:qa[i])
			for (int j=t.l;j<=t.r;j++)
				Q[t.id].ans+=t.sign*(cnt[a[j]+1]+tag[(a[j]+1)/sz+1]);
        
		if (tag[a[i]/sz+1]) for (int j=L[a[i]/sz+1];j<=R[a[i]/sz+1];j++) cnt[j]+=tag[a[i]/sz+1];
		tag[a[i]/sz+1]=0; for (int j=1;j<=a[i]/sz;j++) tag[j]++;
		for (int j=L[a[i]/sz+1];j<=a[i];j++) cnt[j]++;	
	}
	memset(cnt,0,sizeof cnt);
	memset(tag,0,sizeof tag);
	
	for (int i=n;i;i--)
	{
		for (auto t:qb[i])
			for (int j=t.l;j<=t.r;j++)
				if (a[j]>1) Q[t.id].ans+=t.sign*(cnt[a[j]-1]+tag[(a[j]-1)/sz+1]);
        
		if (tag[a[i]/sz+1]) for (int j=L[a[i]/sz+1];j<=R[a[i]/sz+1];j++) cnt[j]+=tag[a[i]/sz+1];
		tag[a[i]/sz+1]=0; for (int j=a[i]/sz+2;j<=blocks;j++) tag[j]++;
		for (int j=a[i];j<=R[a[i]/sz+1];j++) cnt[j]++;
	}
	for (int i=1;i<m;i++) Q[i].ans+=Q[i-1].ans;
	for (int i=0;i<m;i++) ans[Q[i].id]=Q[i].ans;
	for (int i=0;i<m;i++) printf("%lld\n",ans[i]);
	return 0;
}