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

#define int long long
#define rep(i,a,b) for (int i=a; i<(b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int) (x).size()
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
const int maxn = 100000;
const int blk = 350;
const int base = 3;
const int oo1 = 1e9+7;
const int oo2 = 1e9+9;
const int maxx = 1e6;
int n, q;
int a[maxn+1];
int multiplier[maxx+1];
pii value_a[maxn+1];
vector<pii> Q;

pii hash_list[maxn+1];
pii powB[maxx+1];

vector<pii> hash_values;

int cnt[maxn+1];

#define K(x) pii(x.first/blk, x.second ^ -(x.first/blk & 1))

pii ad(pii x, pii y) { return {(x.first + y.first)%oo1, (x.second + y.second)%oo2}; }
pii mult(pii x, int y) { return {x.first*y%oo1, x.second*y%oo2}; }
pii mult(pii x, pii y) { return {x.first*y.first%oo1, x.second*y.second%oo2}; }
pii sub(pii x,pii y) { return {(x.first - y.first + oo1*oo1)%oo1, (x.second - y.second + oo2*oo2)%oo2}; }

int get_index(pii x) {
	return distance(begin(hash_values), lower_bound(all(hash_values), x));
}
main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> q;
	rep(i,0,maxx+1) multiplier[i] = 1;
	rep(i,1,n+1) {
		cin >> a[i];
		if (multiplier[a[i]] == 1) value_a[i] = {1,1};
		else value_a[i] = {oo1 - 1, oo2 - 1};
		multiplier[a[i]] = -multiplier[a[i]];
	}
	
	powB[0] = {1,1};
	rep(i,1,maxx+1) powB[i] = mult(powB[i-1], base);

	rep(i,0,q) {
		int l, r; cin >> l >> r;
		Q.push_back({l-1,r});
	}
	
	hash_list[0] = {0,0};
	rep(i,1,n+1) {
		hash_list[i] = ad(hash_list[i-1], mult(value_a[i], powB[a[i]]));
		//cout << value_a[i].first << ' ' << value_a[i].second << '\n';
		//cout << powB[a[i]].first << ' ' << powB[a[i]].second << '\n';
		//cout << hash_list[i].first << ' ' << hash_list[i].second << '\n';
	}
	
	rep(i,0,n+1) hash_values.push_back(hash_list[i]);
	sort(all(hash_values));
	hash_values.erase(unique(all(hash_values)), end(hash_values));
	
	vi s(sz(Q)), res = s;
	iota(all(s), 0);
	sort(all(s), [&](int s,int t) { return K(Q[s]) < K(Q[t]); });
	
	int L = 0, R = 0;
	cnt[get_index({0,0})]++;
	int total_res = 0;
	for (int qi : s) {
		pii q = Q[qi];
		while (L > q.first) {
			L--;
			int vt = get_index(hash_list[L]);
			total_res += cnt[vt];
			cnt[vt]++;
		}
		while (R < q.second) {
			R++;
			int vt = get_index(hash_list[R]);
			total_res += cnt[vt];
			cnt[vt]++;
		}
		while (L < q.first) {
			int vt = get_index(hash_list[L]);
			cnt[vt]--;
			total_res -= cnt[vt];
			L++;
		}
		while (R > q.second) {
			int vt = get_index(hash_list[R]);
			cnt[vt]--;
			total_res -= cnt[vt];
			R--;
		}
		int length = q.second - q.first;
		/*cout << q.first << ' ' << q.second << '\n';
		rep(i,0,sz(hash_values)) cout << cnt[i] << ' ';
		cout << '\n';*/
		res[qi] = length * (length + 1) / 2 - total_res;
	}
	
	
	rep(i,0,q) cout << res[i] << '\n';
	return 0;
}