#include <bits/stdc++.h>
using namespace std;
using ll = long long;

vector<ll> naive(int N, int Q, vector<int> T, vector<int> D, vector<int> U) {
	vector<ll> ret(Q);
	for (int i = 0; i < Q; ++i) {
		for (int l = 0; l < N; ++l) {
			int mi = N, ma = -1;
			for (int r = l; r < N; ++r) {
				mi = min(mi, T[r]);
				ma = max(ma, T[r]);
				if (mi == D[i] && ma == U[i] - 1) {
					ret[i] += 1;
				}
			}
		}
	}
	return ret;
}

ll coeff(int l, int r) {
	ll n = r - l;
	return n * (n - 1) / 2;
}

vector<ll> solve(int N, int Q, vector<int> T, vector<int> D, vector<int> U) {
	vector<int> start(N + 1);
	for (int i = 0; i < N; ++i) {
		start[T[i]] += 1;
	}
	for (int i = 0; i < N; ++i) {
		start[i + 1] += start[i];
	}
	vector<int> idx(N);
	for (int i = 0; i < N; ++i) {
		idx[--start[T[i]]] = i + 1;
	}

	vector<int> L(4 * Q), R(4 * Q);
	for (int i = 0; i < Q; ++i) {
		L[4 * i + 0] = start[D[i]], R[4 * i + 0] = start[U[i]];
		L[4 * i + 1] = start[D[i]], R[4 * i + 1] = start[U[i] - 1];
		L[4 * i + 2] = start[D[i] + 1], R[4 * i + 2] = start[U[i]];
		L[4 * i + 3] = start[D[i] + 1], R[4 * i + 3] = start[U[i] - 1];
	}
	vector<ll> ans(4 * Q);
	
	constexpr int B = 160;
	const int Buckets = N / B + 1;
	vector<vector<int>> queries(Buckets);
	for (int i = 0; i < 4 * Q; ++i) {
		if (L[i] < R[i]) queries[L[i] / B].push_back(i);
	}
	for (int b = 0; b < Buckets; ++b) {
		auto& qs = queries[b];
		if (qs.empty()) continue;
		sort(begin(qs), end(qs), [&](int i, int j) { return R[i] < R[j]; });
		const int K = min(N, (b + 1) * B);
		vector<int> l(N + 2), r(N + 2);
		for (int i = 0; i <= N; ++i) {
			l[i + 1] = i;
			r[i] = i + 1;
		}
		ll val = 0;
		int t = K;
		vector<array<int, 3>> memo;
		for (const int q : qs) {
			if (R[q] < K) {
				for (int p = L[q]; p < R[q]; ++p) {
					const int k = idx[p];
					int kl = l[k];
					int kr = r[k];
					val -= coeff(kl, k);
					val -= coeff(k, kr);
					val += coeff(kl, kr);
					r[kl] = kr;
					l[kr] = kl;
					memo.push_back({kl, k, kr});
				}
				ans[q] = val;
				while (!memo.empty()) {
					auto [kl, k, kr] = move(memo.back());
					memo.pop_back();
					val += coeff(kl, k);
					val += coeff(k, kr);
					val -= coeff(kl, kr);
					r[kl] = k;
					l[kr] = k;
				}
				continue;
			}
			while (t < R[q]) {
				int k = idx[t++];
				int kl = l[k];
				int kr = r[k];
				val -= coeff(kl, k);
				val -= coeff(k, kr);
				val += coeff(kl, kr);
				r[kl] = kr;
				l[kr] = kl;
			}
			int s = K;
			while (s > L[q]) {
				int k = idx[--s];
				int kl = l[k];
				int kr = r[k];
				val -= coeff(kl, k);
				val -= coeff(k, kr);
				val += coeff(kl, kr);
				r[kl] = kr;
				l[kr] = kl;
				memo.push_back({kl, k, kr});
			}
			ans[q] = val;
			while (!memo.empty()) {
				auto [kl, k, kr] = move(memo.back());
				memo.pop_back();
				val += coeff(kl, k);
				val += coeff(k, kr);
				val -= coeff(kl, kr);
				r[kl] = k;
				l[kr] = k;
			}
		}
	}

	vector<ll> ret(Q);
	for (int i = 0; i < Q; ++i) {
		ret[i] = ans[4 * i + 0] - ans[4 * i + 1] - ans[4 * i + 2] + ans[4 * i + 3];
	}
	return ret;
}

int main() {
	cin.tie(nullptr)->sync_with_stdio(false);

	int N, Q;
	cin >> N >> Q;
	vector<int> T(N);
	for (int i = 0; i < N; ++i) {
		cin >> T[i];
		T[i] -= 1;
	}
	vector<int> D(Q), U(Q);
	for (int i = 0; i < Q; ++i) {
		cin >> D[i] >> U[i];
		D[i] -= 1;
	}

	auto ans = solve(N, Q, T, D, U);
	for (const ll x : ans) {
		cout << x << '\n';
	}
	// cout << flush;
	{
		// auto expected = naive(N, Q, T, D, U);
		// for (const ll x : expected) {
		// 	cerr << x << endl;
		// }
		// assert(ans == expected);
	}

	return 0;
}