考虑莫队二次离线：

设 $F(i,k)$ 为 $[1,k]$ 中大于 $a_i$ 的数的和，$G(i,k)$ 为 $[1,k]$ 中小于 $a_i$ 的数的数量。

左指针移动到 $x$ 造成的答案变化：$F(x,r)-F(x,x)+(G(x,r)-G(x,x)+1)\times a_x$

右指针移动到 $x$ 造成的答案变化：$F(x,x-1)-F(x,l-1)+(G(x,x-1)-G(x,l-1)+1)\times a_x$

按照套路，我们将 $F(x,x-1)=F(x,x)$ 和 $G(x,x-1)=G(x,x)$ 的值都通过树状数组预处理出来，莫队的时候直接处理；剩余部分二次离线后使用扫描线处理，由于莫队的指针移动连续，我们对于一次连续的移动只需要记录一次，一次询问最多发生两次连续的指针挪动，所以这部分空间复杂度 $O(m)$。

扫描线时需要注意，莫队指针移动路径的总长度为 $O(n\sqrt m)$，所以我们需要 $O(1)$ 查询的数据结构，由于只有 $O(n)$ 次插入，所以插入复杂度不能超过 $O(\sqrt n)$，使用分块即可。

最后记得将答案求前缀和，具体的原因是询问 $i$ 处的指针移动对询问 $[i,m]$ 会产生影响。

空间复杂度：$O(a_i+n+m)$ 时间复杂度：$O(n\sqrt m+n\sqrt {a_i})$

下面给出代码，不懂得可以照着代码理解一下。温馨提示：记得开 long long。

#include<cstdio>
#include<cmath>
#include<algorithm>
#include<vector>
#include<tuple>
namespace IO{
	#define BUFSIZE 10000000
	struct read{
		char buf[BUFSIZE],*p1,*p2,c,f;
		read():p1(buf),p2(buf){}
		char gc(void){
			if(p1==p2)p2=buf+fread(p1=buf,1,BUFSIZE,stdin);
			if(p1==p2)return EOF;
			else return *p1++;
		}
		read& operator >>(int& x){
			c=gc(),f=1,x=0;
			for(;c<'0'||c>'9';c=gc())if(c=='-')f=-1;
			for(;c>='0'&&c<='9';c=gc())x=x*10+c-'0';
			x*=f;
			return *this;
		}
	};
	struct write{
		char buf[BUFSIZE],*p1,*p2,s[50];
		int tp;
		write():p1(buf),p2(buf+BUFSIZE){}
		~write(){flush();}
		void flush(void){
			fwrite(buf,1,p1-buf,stdout);
			p1=buf;
		}
		void pc(char c){
			if(p1==p2)flush();
			*p1++=c;
		}
		write& operator <<(long long x){
			if(x<0)x=-x,pc('-');
			do{s[tp++]=x%10+'0',x/=10;}while(x);
			while(tp)pc(s[--tp]);
			return *this;
		}
		write& operator <<(char x){
			pc(x);
			return *this;
		}
	};
	read in;
	write out;
}
using IO::in;
using IO::out;
int n,m,a[500010],bel[500010],sz,belv[100010],rv[320];
long long c[100010],f[500010],g[500010],ans[500010],t[100010];
inline void updated(int i,long long const &x,long long *c){//树状数组
	for(;i<=100000;i+=i&-i)c[i]+=x;
}
inline long long queryd(int i,long long *c){
	long long res(0);
	for(;i;i-=i&-i)res+=c[i];
	return res;
}
struct node{
	int l,r,id;
	inline bool operator <(node const &x)const{
		return bel[l]==bel[x.l]?r<x.r:l<x.l;
	}
}q[500010];
std::vector<std::tuple<int,int,int,int> > v[500010];
long long fs[350],fv[100010],gs[350],gv[100010];
inline void update(int const &p,int const &k,long long *s,long long *sv){//分块
	for(int i=belv[p],j=belv[100000];i<=j;i++) s[i]+=k;
	for(int i=p,j=rv[belv[p]];i<=j;i++) sv[i]+=k;
}
inline long long query(int const &p,long long *s,long long *sv){
	return s[belv[p]-1]+sv[p];
}
int main(){
	in>>n>>m;
	::sz=317;
	for(int i=1;i<=100000;i++)belv[i]=(i-1)/::sz+1;
	for(int i=0,j=1;i<=100000;i+=::sz,j++)rv[j-1]=i;//分块
	rv[belv[100000]]=100000;
	int sz=n/sqrt(m+1)+1;
	for(int i=1;i<=n;i++)in>>a[i],bel[i]=(i-1)/sz+1;//莫队分块
	for(int i=1;i<=m;i++)in>>q[i].l>>q[i].r,q[i].id=i;
	std::sort(q+1,q+m+1);
	for(int i=1;i<=n;i++){//预处理
		updated(a[i],a[i],c);
		f[i]=queryd(100000,c)-queryd(a[i],c);
		g[i]=queryd(a[i]-1,t);
		updated(a[i],1,t);
	}
	for(int i=1,l=1,r=0;i<=m;i++){//莫队
		if(l>q[i].l) v[r].emplace_back(q[i].l,l-1,1,q[i].id);
		while(l>q[i].l) --l,ans[q[i].id]-=f[l]+(g[l]-1)*a[l];
		if(r<q[i].r) v[l-1].emplace_back(r+1,q[i].r,-1,q[i].id);
		while(r<q[i].r)	++r,ans[q[i].id]+=f[r]+(g[r]+1)*a[r];
		if(l<q[i].l) v[r].emplace_back(l,q[i].l-1,-1,q[i].id);
		while(l<q[i].l) ans[q[i].id]+=f[l]+(g[l]-1)*a[l],++l;
		if(r>q[i].r) v[l-1].emplace_back(q[i].r+1,r,1,q[i].id);
		while(r>q[i].r) ans[q[i].id]-=f[r]+(g[r]+1)*a[r],--r;
	}
	for(int p=1;p<=n;p++){//扫描线
		int l,r,kt,id;
		update(a[p],a[p],fs,fv),update(a[p],1,gs,gv);
		for(auto&& x:v[p]){
			std::tie(l,r,kt,id)=x;
			for(int i=l;i<=r;i++)
				ans[id]+=kt*(query(100000,fs,fv)-query(a[i],fs,fv)+query(a[i]-1,gs,gv)*a[i]);
		}
	}
	for(int i=2;i<=m;i++)ans[q[i].id]+=ans[q[i-1].id];//前缀和
	for(int i=1;i<=m;i++)out<<ans[i]<<'\n';
	return 0;
}