#include <bits/stdc++.h>

using namespace std;
const int N = 5e5 + 100;
inline int read() {
	int q=0,w=1;char c=getchar();
	while(!isdigit(c)){if(c=='-')w=-1;c=getchar();}
	while(isdigit(c))q=q*10+c-'0',c=getchar();
	return w*q;
}

struct node {
	int l, r, id, bel;
	inline bool operator < (const node &b) const {
		if(bel == b.bel) return r < b.r;
		return l < b.l;
	}
}Q[N];
int n, m, block, col[N], cnt[N], Ans[N];

int main() {
	n = read(); m = read(); block = sqrt(n);
	for(int i = 1;i <= n; ++i) col[i] = read();
	for(int i = 1;i <= m; ++i) {
		Q[i].l = read();
		Q[i].r = read();
		Q[i].id = i;
		Q[i].bel = (Q[i].l + 1) / block;
	}
	sort(Q + 1, Q + 1 + m);
	int l = 1, r = 0, ans = 0;
	for(int i = 1;i <= m; ++i) {
		int ql = Q[i].l, qr = Q[i].r;
        while(l < ql) ans -= !--cnt[col[l++]];
        while(l > ql) ans += !cnt[col[--l]]++;
        while(r < qr) ans += !cnt[col[++r]]++;
        while(r > qr) ans -= !--cnt[col[r--]];
        Ans[Q[i].id] = ans;
	}
	for(int i = 1;i <= m; ++i) 
		printf("%d\n", Ans[i]);
	return 0;
}