RT，WA前两个点。

二次离线莫队，思路跟题解差不多，但是同时计算了比当前值大的数的和以及比当前的数小的个数，都是值域分块维护，再额外加区间的和。pre[i]是第i个数对 $1\sim i-1$ 区间的变化量。

有一点不是特别清楚，就是区间左移写成前缀之差时前缀区间包含当前点应该怎么处理，能不能不改用后缀。现在这样是完全忽略，也不知道有没有问题。

另外很奇怪，后面的16个数据点左端点移动写错都不改变答案。

#include <bits/stdc++.h>
using namespace std;
template<typename T>
void read(T &x){
	x=0; register int f=1; register char c=getchar();
	while(c>'9'||c<'0') {if (c=='-') f=-1;c=getchar();}
	while(c<='9'&&c>='0') x=(x<<1)+(x<<3)+(c^48),c=getchar();
	x*=f;
}
const int MAXN=5e6+10;
const int MAXV=1e6+10;
const int MAXsV=1e3+10;

struct Query{
	int l,r,id,pos;
	long long ans;
	friend bool operator<(Query a,Query b){
		if (a.pos==b.pos) return a.r<b.r;
		return a.pos<b.pos;
	}
}q[MAXN];

vector < tuple <int,int,int,int> > v[MAXN];

int n,m,a[MAXN],
	len,num,maxv,l,r,
	val2[MAXV],tag2[MAXsV];
long long val1[MAXV],tag1[MAXsV],pre[MAXN],sum[MAXN],ans[MAXN];
#define lbd(i) ((i-1)*len+1)
#define rbd(i) ((i==num)?maxv:i*len)
#define bl(x) ((x-1)/len+1)
#define get(v) ( val1[v]+tag1[bl(v)]+1ll*v*(val2[v]+tag2[bl(v)]) )


inline void add(int v){
	int pos=bl(v),lb=lbd(pos),rb=rbd(pos);
	for (int i=lb;i<=v-1;i++) val1[i]+=v;
	for (int i=1;i<=pos-1;i++) tag1[i]+=v;
	for (int i=v+1;i<=rb;i++) val2[i]++;
	for (int i=pos+1;i<=num;i++) tag2[i]++;
}

int main(){
	read(n);read(m);
	for (int i=1;i<=n;i++) {read(a[i]);maxv=max(maxv,a[i]);sum[i]=sum[i-1]+a[i];}
	len=sqrt(n);num=maxv/len;if (maxv%len) num++;
	for (int i=1;i<=m;i++){
		read(q[i].l);read(q[i].r);q[i].id=i;q[i].pos=bl(q[i].l);
	}
	sort(q+1,q+m+1);
	for (int i=1;i<=n;i++){
		pre[i]=get(a[i]);
		add(a[i]);
	}
	memset(tag1,0,sizeof tag1);
	memset(val1,0,sizeof val1);
	memset(tag2,0,sizeof tag2);
	memset(val2,0,sizeof val2);
	l=1;
	for (int i=1;i<=m;i++){
		int ql=q[i].l,qr=q[i].r;
		if (r<qr) v[l-1].emplace_back(r+1,qr,i,-1);
		while(r<qr) q[i].ans+=pre[++r];
		if (l>ql) v[r].emplace_back(ql,l-1,i,1);
		while(l>ql) q[i].ans-=pre[--l];
		if (r>qr) v[l-1].emplace_back(qr+1,r,i,1);
		while(r>qr) q[i].ans-=pre[r--];
		if (l<ql) v[r].emplace_back(l,ql-1,i,-1);
		while(l<ql) q[i].ans+=pre[l++];
	}
	for (int i=1;i<=n;i++){
		add(a[i]);
		for (int j=0;j<v[i].size();j++){
			tuple<int,int,int,int> x=v[i][j];
			for (int p=get<0>(x);p<=get<1>(x);p++){
				q[get<2>(x)].ans+=1ll*get(a[p])*get<3>(x);
			}
		}
	}
	for (int i=1;i<=m;i++) {
		q[i].ans+=q[i-1].ans;
		ans[q[i].id]=q[i].ans+(sum[q[i].r]-sum[q[i].l-1]);
	}
	for (int i=1;i<=m;i++) printf("%lld\n",ans[i]);
	return 0;
}
//f(x,l->r):区间内比严格大于它的数的和+（区间内比它小的数的个数+1）*它自己的值,那个1单独处理