#include <bits/stdc++.h>
#define int long long
using namespace std;
int n, m, a[500005], ans[500005];
struct que {
	int l, r, name;
} c[500005];
struct node {
	int l, r, sum, maxn, addtag, changetag, tadd;
} b[2000006];
struct nnode {
	int name, num;
} r[500005];
int l;
bool cmp(que p, que q) {
	return p.r < q.r;
}
inline void update(int p) {
	b[p].sum = b[2 * p].sum + b[2 * p + 1].sum;
	b[p].maxn = b[2 * p].maxn + b[2 * p + 1].maxn;
}
inline void push_down(int p) {
	if (b[p].tadd) {
		b[2 * p].tadd += b[p].tadd;
		b[2 * p + 1].tadd += b[p].tadd;
		b[2 * p].sum += (b[2 * p].r - b[2 * p].l + 1) * b[p].tadd;
		b[2 * p + 1].sum += (b[2 * p + 1].r - b[2 * p + 1].l + 1) * b[p].tadd;
		b[p].tadd = 0;
	}
	if (b[p].addtag) {
		if (b[2 * p].changetag) {
			b[2 * p].tadd += b[2 * p].changetag * b[p].addtag;
			b[2 * p].sum += (b[2 * p].r - b[2 * p].l + 1) * b[2 * p].changetag * b[p].addtag;
		} else {
			b[2 * p].addtag += b[p].addtag;
			b[2 * p].sum +=  b[p].addtag * b[2 * p].maxn;
		}
		if (b[2 * p + 1].changetag) {
			b[2 * p + 1].tadd += b[2 * p + 1].changetag * b[p].addtag;
			b[2 * p + 1].sum += (b[2 * p + 1].r - b[2 * p + 1].l + 1) * b[2 * p + 1].changetag * b[p].addtag;
		} else {
			b[2 * p + 1].addtag += b[p].addtag;
			b[2 * p + 1].sum +=  b[p].addtag * b[2 * p + 1].maxn;
		}
		b[p].addtag = 0;
	}
	if (b[p].changetag) {
		b[2 * p].changetag = b[2 * p + 1].changetag = b[p].changetag;
		b[2 * p].maxn = (b[2 * p].r - b[2 * p].l + 1) * b[p].changetag;
		b[2 * p + 1].maxn = (b[2 * p + 1].r - b[2 * p + 1].l + 1) * b[p].changetag;
		b[p].changetag = 0;
	}
}
inline void build(int p, int l, int r) {
	b[p].l = l, b[p].r = r;
	b[p].addtag = b[p].changetag = b[p].tadd = 0;
	b[p].sum = b[p].maxn = 0;
	if (l == r) {
		return;
	}
	build(2 * p, l, (l + r) >> 1);
	build(2 * p + 1, ((l + r) >> 1) + 1, r);
}
inline void change(int p, int l, int r, int w) {
	if (b[p].l >= l && b[p].r <= r) {
		b[p].changetag = w;
		b[p].maxn = (b[p].r - b[p].l + 1) * w;
		return;
	}
	push_down(p);
	int mid = (b[p].r + b[p].l) >> 1;
	if (r <= mid) change(2 * p, l, r, w);
	else if (l > mid) change(2 * p + 1, l, r, w);
	else change(2 * p, l, mid, w), change(2 * p + 1, mid + 1, r, w);
	update(p);
}
inline int query(int p, int l, int r) {
	if (b[p].l >= l && b[p].r <= r) {
		return b[p].sum;
	}
	push_down(p);
	int mid = (b[p].r + b[p].l) >> 1;
	if (r <= mid) return query(2 * p, l, r);
	else if (l > mid) return query(2 * p + 1, l, r);
	else return query(2 * p, l, mid) + query(2 * p + 1, mid + 1, r);
}
inline void add(int p, int l, int r) {
	if (b[p].l >= l && b[p].r <= r) {
		if (b[ p].changetag) {
			b[p].tadd += b[p].changetag;
			b[p].sum += (b[p].r - b[p].l + 1) * b[p].changetag;
		} else {
			b[p].addtag += 1;
			b[p].sum +=  b[p].maxn;
		}
		return;
	}
	push_down(p);
	int mid = (b[p].r + b[p].l) >> 1;
	if (r <= mid) add(2 * p, l, r);
	else if (l > mid) add(2 * p + 1, l, r);
	else add(2 * p, l, mid), add(2 * p + 1, mid + 1, r);
	update(p);
}
inline void update(nnode u) {
	int ll = 0, rr = l, mid;
	while (ll < rr) {
		mid = (ll + rr + 1) >> 1;
		if (r[mid].num >= u.num) {
			ll = mid;
		} else {
			rr = mid - 1;
		}
	}
	r[ll + 1] = u;
//	cout << r[ll].name + 1 << "|" << u.name << "|" << u.num << endl;
	l = ll + 1;
	change(1, r[ll].name + 1, u.name, u.num);
	add(1, 1, u.name);
}
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	for (int i = 1; i <= m; i++) {
		cin >> c[i].l >> c[i].r;
		c[i].name = i;
	}
	sort(c + 1, c + m + 1, cmp);
	r[0].num = 0x3f3f3f3f;
	build(1, 1, n);
	int cnt = 0;
	for (int i = 1; i <= n; i++) {
		update(nnode{i, a[i]});
		while (cnt + 1 <= m && c[cnt + 1].r <= i) {
			cnt++;
			ans[c[cnt].name] = query(1, c[cnt].l, c[cnt].r);
		}
	}
	for (int i = 1; i <= m; i++) {
		cout << ans[i] << "\n";
	}
}
//3 6
//1 3 2
//1 1
//1 2
//1 3
//2 2
//2 3
//3 3