#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 500005;

int ft[N];

void add(int x, int val) {
	x++;
	for(; x < N; x += x & -x) {
		ft[x] += val;
	}
}
int get(int x) {
	x++;
	int ans = 0;
	for(; x > 0; x -= x & -x) ans += ft[x];
	return ans;
}

int n, q;
int a[N];
int ans[N];
int last[N];

vector<int> rem[N];
vector<pair<int, int>> put[N];

int main() {
	scanf("%d %d", &n, &q);

	for(int i = 1; i <= n; i++) scanf("%d", a + i);

	for(int i = 0; i < q; i++) {
		int l, r;
		scanf("%d %d", &l, &r);
		rem[l - 1].push_back(i);
		put[r].emplace_back(i, l);
	}
	
	for(int i = 1; i <= n; i++) {
		add(last[ a[i] ], 1);
		last[ a[i] ] = i;
		for(int id : rem[i]) {
			ans[id] -= get(i);
		}
		for(pair<int, int> e : put[i]) {
			int id, l;
			tie(id, l) = e;
			ans[id] += get(l - 1);
		}
	}

	for(int i = 0; i < q; i++) {
		printf("%d\n", ans[i]);
	}
	
}
