#include<bits/stdc++.h>
using namespace std;
unsigned long long a[200005], cnt[200005], ans[200005], n, m, b, sum = 0;
struct Q {
	long long l = -1, r = -1, id = -1;
	bool operator < (Q a) {
		if (l / b != a.l / b) return l < a.l;
		return r < a.r;
	}
} q[200005];
void add(int x) {
	if (++cnt[x] >= 3) sum += (cnt[x] - 1) * (cnt[x] - 2) / 2;
}
void del(int x) {
	if (cnt[x]-- >= 3) sum -= cnt[x] * (cnt[x] - 1) / 2;
}
int main() {
	memset(cnt, 0, sizeof(cnt));
	cin >> n >> m;
	for (int i = 1; i <= n; i++) cin >> a[i];
	for (int i = 1; i <= m; i++) {
		cin >> q[i].l >> q[i].r;
		q[i].id = i;
	}
	b = sqrt(n * n / m * 1.0);
	sort(q + 1, q + m + 1);
	for (int k = 1, i = 1, j = 0; k <= m; k++) {
		while (j < q[k].r) add(a[++j]);
		while (i > q[k].l) add(a[--i]);
		while (j > q[k].r) del(a[j--]);
		while (i < q[k].l) del(a[i++]);
		ans[q[k].id] = sum;
	}
	for (int i = 1; i <= m; i++) cout << ans[i] << endl;
	return 0;
}

莫名地RE 求Dalao帮个忙看看