// first second push_back unordered return continue break vector visited check flag bool while iterator begin end lower_bound upper_bound temp true false ll_MAX ll_MIN insert erase clear pop push compare ll64_MAX ll64_MIN  reverse replace stringstream string::npos length substr front priority_queue

#ifndef ONLINE_JUDGE
#include "debug.h"
#else
#include <bits/stdc++.h>
using namespace std;
#define debug(...) 42
#endif

#define ll long long
#define all(a)      (a).begin(),(a).end()
using pll = pair < ll, ll >;

const ll sz = 8e5 + 10;
vector<vector<ll>> tree(sz);
vector<vector<ll>> pre(sz);
vector<ll> sum(sz);
ll curVal;

void merge(ll node, ll x, ll y) {
	ll i = 0, j = 0;
	tree[node].clear();
	pre[node].clear();
	sum[node] = 0;

	while (i < tree[x].size()) {
		tree[node].push_back(tree[x][i]);
		i++;
	}

	i = 0;
	if (tree[node].size())	i = tree[node].back();

	while (j < tree[y].size()) {
		ll t = max(i, tree[y][j]);
		sum[node] += t - tree[y][j];
		tree[node].push_back(t);
		j++;
	}

	i = j = 0;
	while (i < tree[node].size()) {
		j += tree[node][i];	i++;
		pre[node].push_back(j);
	}
}

void update(ll node, ll l, ll r, ll idx, ll val) {
	if (l > r)	return;
	if (l == r) {
		tree[node] = {val};
		pre[node] = {val};
		return;
	}

	ll mid = (l + r) / 2;
	if (idx <= mid)	update(2 * node, l, mid, idx, val);
	else	update(2 * node + 1, mid + 1, r, idx, val);

	merge(node, node * 2, node * 2 + 1);
}

ll get(ll node, ll l, ll r, ll rangeL, ll rangeR, ll &val) {
	if (l > r or l > rangeR or r < rangeL)	return 0;

	if (rangeL <= l and r <= rangeR)	{
		ll x = sum[node];
		if (tree[node].size() != 0) {
			ll i = lower_bound(all(tree[node]), val) - tree[node].begin();
			if (i > 0)	x += (i * val) - pre[node][i - 1];
			val = max(val, tree[node].back());
		}
		return x;
	}

	ll mid = (l + r) / 2;
	ll idx = get(node * 2, l, mid, rangeL, rangeR, val);
	idx += get(node * 2 + 1, mid + 1, r, rangeL, rangeR, val);
	return idx;
}


int32_t main() {
	ios::sync_with_stdio(0); 		cin.tie(0); cout.tie(0);

	ll t, i, j, y, x, n, z, k;
	cin >> n >> t;
	vector<ll> val, ans;

	for (ll i = 1; i <= n; i++) {
		cin >> x;	val.push_back(x);
		update(1, 1, n, i, x);
	}

	while (t--) {
		cin >> x >> y;
		ll mn = 0;
		z = get(1, 1, n, x, y, mn);
		ans.push_back(z);
	}

	debug(ans);
	for (auto &zx : ans)	cout << zx << " ";
}