#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
#include<map>

using namespace std;

struct Query {
	int L, R, i;
	Query() {}
	Query(int left, int right, int idx): L(left), R(right), i(idx) {}
};

const int maxn = 2e5 + 5;
int n, q, x, y, A[maxn], B[maxn], fenwick[maxn];
vector<Query> queries;
vector<int> ans;
map<int, int> seen;

bool cmp(Query &q1, Query &q2) {
	return q1.L < q2.L;
}

void upd(int i, int v) { // fenwick tree is 1-indexed
	if(i == 0) return;
	int c = i;
	while(c <= n) {
		fenwick[c] += v;
		c += (c & -c);
	}
}

int qr(int i) { // fenwick tree is 1-indexed
	if(i == 0) return 0;
	int c = i, ans = 0;
	while(c > 0) {
		ans += fenwick[c];
		c -= (c & -c);
	}
	return ans;
}

void printFenwick() {
	for(int i = 1; i <= n; i++) {
		cout << qr(i) - qr(i - 1) << " ";
	}
	cout << '\n';
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> q;
	for(int i = 1; i <= n; i++) {
		cin >> A[i];
	}
	for(int i = n; i > 0; i--) {
		if(seen.count(A[i]) != 0) B[i] = seen[A[i]];
		seen[A[i]] = i;
	}
	seen.clear();
	for(int i = 1; i <= n; i++) {
		if(seen.count(A[i]) == 0) upd(i, 1);
		seen[A[i]] = 1;
	}
	queries.resize(q), ans.resize(q);
	for(int i = 0; i < q; i++) {
		cin >> x >> y;
		queries[i] = {x, y, i};
	}
	sort(queries.begin(), queries.end(), cmp);
	for(int i = 0, beforeL = 1; i < q; i++) {
		int curL = queries[i].L, curR = queries[i].R;
		while(beforeL < curL) {
			upd(B[beforeL], 1);
			beforeL++;
		}
		ans[queries[i].i] = qr(curR) - qr(curL - 1);
	}
	for(auto &qr_ans : ans) cout << qr_ans << '\n';
	return 0;
}