求助各路奆老（码风不好请原谅）

# include <bits/stdc++.h>
# define endl '\n'
# define int long long
# define Max ((int) (1e5 + 5))

using namespace std;

int n, q, x[Max],  bl[Max], sze, lst[Max], nxt[Max], z[Max], zz, st[Max][30], lg[Max], nl = 1, nr = 0;

struct node
{
	int id;
	int l;
	int r;
	long long ret;
} w[Max];

inline bool cmp1(node a, node b)
{
	return bl[a.l] ^ bl[b.l] ? bl[a.l] < bl[b.l] : a.r < b.r;
}

inline bool cmp2(node a, node b)
{
	return a.id < b.id;
}

inline int ask(int a, int b)
{
	return x[a] > x[b] ? b : a;
}

inline long long rig()
{
	int len = nr - nl + 1, pos = ask(st[nl][lg[len]], st[nr - (1 << lg[len]) + 1][lg[len]]);
	return lst[nr] - lst[pos] + x[pos] * (pos - nl + 1);
}

inline long long lef()
{
	int len = nr - nl + 1, pos = ask(st[nl][lg[len]], st[nr - (1 << lg[len]) + 1][lg[len]]);
	return nxt[nl] - nxt[pos] + x[pos] * (nr - pos + 1);
}

signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cin >> n >> q;
	sze = sqrt(n);
	int js = sze;
	for (int i = 1; i <= n; i++)
	{
		lg[i] = lg[i - 1] + ((1 << lg[i - 1]) == 1);
	}
	for (int i = 1; i <= n; i++)
	{
		lg[i]--;
	}
	for (int i = 1; i <= n; i++)
	{
		cin >> x[i];
		++js;
		bl[i] = bl[i - 1];
		if (js > sze)
		{
			js = 1;
			bl[i]++;
		}
	}
	for (int i = 1; i <= q; i++)
	{
		cin >> w[i].l >> w[i].r;
		w[i].id = i;
	}
	sort (w + 1, w + q + 1, cmp1);
	for (int i = 1; i <= n; i++)
	{
		while (zz > 0 && x[z[zz]] >= x[i])
		{
			--zz;
		}
		lst[i] = lst[z[zz]] + (i - z[zz]) * x[i];
		z[++zz] = i;
	}
	zz = 0;
	z[zz] = n + 1;
	for (int i = n; i >= 1; i--)
	{
		while (zz > 0 && x[z[zz]] >= x[i])
		{
			--zz;
		}
		nxt[i] = nxt[z[zz]] + (z[zz] - i) * x[i];
		z[++zz] = i;
	}
	for (int i = 1; i <= n; i++)
	{
		st[i][0] = i;
	}
	for (int j = 1; j <= 20; j++)
	{
		for (int i = 1; i <= n; i++)
		{
			st[i][j] = ask(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
		}
	}
	int ans = 0;
	for (int i = 1; i <= q; i++)
	{
		while (nr < w[i].r)
		{
			nr++;
			ans += rig();
		}
		while (nl > w[i].l)
		{
			nl--;
			ans += lef();
		}
		while (nl < w[i].l)
		{
			ans -= lef();
			nl++;
		}
		while (nr > w[i].r)
		{
			ans -= rig();
			--nr;
		}
		w[i].ret = ans;
	}
	sort(w + 1, w + q + 1, cmp2);
	for (int i = 1; i <= q; i++)
	{
		cout << w[i].ret << endl;
	}
	return 0;
}