segtree<ll> t,c;
ll n,q,a[2d5],l[2d5],r[2d5],j[2d5],z[1d5];
{
	rd(n,q,((a+q))(n),(a,l,r,a)(q));
	rep(i,q)j[i]=i;
	rep(i,n)j[i+q]=i;
	t.walloc(n,1);
	c.walloc(n,1);
	sortA(n+=q,a,l,r,j);
	for(;n--;){
		if(l[n]){
			z[j[n]]=t.getSum(l[n]-1,r[n])-c.getSum(l[n]-1,r[n])*a[n];
		}else{
			t.add(j[n],j[n]+1,a[n]);
			c.add(j[n],j[n]+1,1);
		}
	}
	wtLn(z(q));
}