RT，对着代码卡了一晚上+一下午的常了，还是没有什么曙光。

最后两个点T飞，前面的点都跑得飞快。

测了一下主要时间花在第二次离线上，可能是写得太丑了。

块长是贺的，快读也是贺的。

码风是vscode格式化码风，有注释。

好人一生平安。

/*sum_{l'~l-1}(bigger[1,r]-bigger[1,i-1]+(smaller[1,r]-smaller[1,i-1]+1)*num[i])*/

#include <bits/stdc++.h>
using namespace std;
const int MAX = 1e6 + 7;
struct query//原询问
{
	int l, r;
	int id;
} q[MAX];
int N, Q;
int block[MAX];//分块的块
int blockk[MAX];//莫队的块
bool cmp(query a, query b)
{
	if (blockk[a.l] != blockk[b.l])
	{
		return a.l < b.l;
	}
	return a.r < b.r;
}
struct seg//离线下来的询问
{
	int l, r;
	int id, opt;
	seg(int a = 0, int b = 0, int c = 0, int d = 0)
	{
		l = a;
		r = b;
		id = c;
		opt = d;
	}
};
vector<seg> v[MAX];//每个元素上挂的询问们
struct BIT//树状数组
{
	long long tree[MAX];
	int lowbit(int x)
	{
		return x & (-x);
	}
	void update(int x, int k)
	{
		while (x <= N)
		{
			tree[x] += k;
			x += lowbit(x);
		}
	}
	long long query(int x)
	{
		long long res = 0;
		while (x > 0)
		{
			res += tree[x];
			x -= lowbit(x);
		}
		return res;
	}
};

BIT A1, A2;//两个BIT，一个统计元素值和，一个元素个数

int ls[MAX / 300], rs[MAX / 300];//分块的块左右界
long long bigger[MAX], smaller[MAX];//比num[i]大的数值总和、比num[i]小的数值个数
struct sqrtblock//分块
{

	long long sumb[MAX / 300], sumv[MAX];//sumb大块的前缀和、sumv单个元素在块内的前缀和
	inline void update(int p, int k)
	{
		for (register int i = block[p]; i <= block[N]; i++)
		{
			sumb[i] += k;
		}
		for (register int i = p; i <= rs[block[p]]; i++)
		{
			sumv[i] += k;
		}
	}
	inline long long getcnt(int p)
	{
		return sumb[block[p] - 1] + sumv[p];
	}
};
sqrtblock B1, B2;//两个分块，一个统计元素值和，一个元素个数

inline void pre()//预处理分块
{
	int M = 317;//分块块长（贺）
	int B = N / M;//分出的块数
	int S = N / (sqrt(Q));//莫队块长
	for (register int i = 1; i <= N; i++)
	{
		block[i] = (i - 1) / M + 1;
		blockk[i] = (i - 1) / S + 1;
	}
	for (register int i = 1; i <= B; i++)
	{
		ls[i] = rs[i - 1] + 1;
		rs[i] = ls[i] + M - 1;
	}
	if (N % M)//边角料
	{
		B++;
		ls[B] = rs[B - 1] + 1;
		rs[B] = N;
	}
}

int num[MAX];
long long ans[MAX];

/*贺来的快读*/

// begin fast read template by CYJian (source: https://www.luogu.com.cn/paste/i11c3ppx)

namespace io
{
	const int __SIZE = (1 << 21) + 1;
	char ibuf[__SIZE], *iS, *iT, obuf[__SIZE], *oS = obuf, *oT = oS + __SIZE - 1, __c, qu[55];
	int __f, qr, _eof;
#define Gc() (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, __SIZE, stdin), (iS == iT ? EOF : *iS++)) : *iS++)
	inline void flush()
	{
		fwrite(obuf, 1, oS - obuf, stdout), oS = obuf;
	}
	inline void gc(char &x) { x = Gc(); }
	inline void pc(char x)
	{
		*oS++ = x;
		if (oS == oT)
			flush();
	}
	inline void pstr(const char *s)
	{
		int __len = strlen(s);
		for (__f = 0; __f < __len; ++__f)
			pc(s[__f]);
	}
	inline void gstr(char *s)
	{
		for (__c = Gc(); __c < 32 || __c > 126 || __c == ' ';)
			__c = Gc();
		for (; __c > 31 && __c < 127 && __c != ' '; ++s, __c = Gc())
			*s = __c;
		*s = 0;
	}
	template <class I>
	inline bool gi(I &x)
	{
		_eof = 0;
		for (__f = 1, __c = Gc(); (__c < '0' || __c > '9') && !_eof; __c = Gc())
		{
			if (__c == '-')
				__f = -1;
			_eof |= __c == EOF;
		}
		for (x = 0; __c <= '9' && __c >= '0' && !_eof; __c = Gc())
			x = x * 10 + (__c & 15), _eof |= __c == EOF;
		x *= __f;
		return !_eof;
	}
	template <class I>
	inline void print(I x)
	{
		if (!x)
			pc('0');
		if (x < 0)
			pc('-'), x = -x;
		while (x)
			qu[++qr] = x % 10 + '0', x /= 10;
		while (qr)
			pc(qu[qr--]);
	}
	struct Flusher_
	{
		~Flusher_() { flush(); }
	} io_flusher_;
} // namespace io
using io::gc;
using io::gi;
using io::gstr;
using io::pc;
using io::print;
using io::pstr;

// end fast read template by CYJian

int tmp[MAX];//离散化数组
void lsh()//离散化
{
	sort(tmp + 1, tmp + 1 + N);
	for (register int i = 1; i <= N; i++)
	{
		num[i] = lower_bound(tmp + 1, tmp + 1 + N, num[i]) - tmp;
	}
}
signed main()
{
	cin >> N >> Q;
	for (register int i = 1; i <= N; i++)
	{
		gi(num[i]);
		tmp[i] = num[i];
	}
	pre();
	lsh();
	for (register int i = 1; i <= N; i++)//预处理num[i]在[1,i-1]中的贡献
	{
		A1.update(num[i], tmp[num[i]]);
		bigger[i] = A1.query(N) - A1.query(num[i]);
		smaller[i] = A2.query(num[i] - 1);
		A2.update(num[i], 1);
	}
	for (register int i = 1; i <= Q; i++)
	{
		gi(q[i].l);
		gi(q[i].r);
		q[i].id = i;
	}
	sort(q + 1, q + 1 + Q, cmp);
	int L = 1, R = 0;
	for (register int i = 1; i <= Q; i++)//空跑莫队，刷询问
	{
		if (L > q[i].l)
		{
			v[R].push_back(seg(q[i].l, L - 1, q[i].id, 1));
		}
		while (L > q[i].l)
		{
			L--;
			ans[q[i].id] -= (bigger[L] + (smaller[L] - 1) * tmp[num[L]]);//tmp[num[i]]就是元素离散化前的值了
		}
		if (R < q[i].r)
		{
			v[L - 1].push_back(seg(R + 1, q[i].r, q[i].id, -1));
		}
		while (R < q[i].r)
		{
			R++;
			ans[q[i].id] += (bigger[R] + (smaller[R] + 1) * tmp[num[R]]);
		}
		if (L < q[i].l)
		{
			v[R].push_back(seg(L, q[i].l - 1, q[i].id, -1));
		}
		while (L < q[i].l)
		{
			ans[q[i].id] += (bigger[L] + (smaller[L] - 1) * tmp[num[L]]);
			L++;
		}
		if (R > q[i].r)
		{
			v[L - 1].push_back(seg(q[i].r + 1, R, q[i].id, 1));
		}
		while (R > q[i].r)
		{
			ans[q[i].id] -= (bigger[R] + (smaller[R] + 1) * tmp[num[R]]);
			R--;
		}
	}
    
	for (register int i = 1; i <= N; i++)//第二次离线，大概率这里写屎了
	{
		B1.update(num[i], tmp[num[i]]);
		B2.update(num[i], 1);
        
		for (register int j = 0; j < v[i].size(); j++)//扫一遍数组，处理挂着的询问
		{
			seg t = v[i][j];
			for (register int k = t.l; k <= t.r; k++)
			{
				ans[t.id] += t.opt * (B1.getcnt(N) - B1.getcnt(num[k]) + (B2.getcnt(num[k] - 1) * tmp[num[k]]));
			}
		}
	}
    
	for (register int i = 1; i <= Q; i++)//前缀和
	{
		ans[q[i].id] += ans[q[i - 1].id];
	}
	for (register int i = 1; i <= Q; i++)
	{
		cout << ans[i] << '\n';
	}
}