#include <bits/stdc++.h>
#define l(x) (x&-x)
const int N=1e6+5;
using namespace std;
int a[N],book[N],ans[N];
int n,m;
template<typename tp>inline void r(tp &n){
	n=0;char c=getchar();
	while(c<'0'||c>'9') c=getchar();
	while(c<='9'&&c>='0') n=(n<<1)+(n<<3)+c-48,c=getchar();
}
template<typename tp>inline void w(tp  n){
	if(n<0) putchar('-'),n=-n;
	if(n/10) w(n/10);
	putchar(n%10+48);
}
struct Section{
	int x,y,id;
}sec[N];
struct TA{
	int c[N];
	void A(int p,int v){
		while(p<=n)
			c[p]+=v,p+=l(p);
	}
	int  G(int p){
		int ret=0;
		while(p)
			ret+=c[p],p-=l(p);
		return ret;
	}
}t;
bool Cmp(Section a,Section b){
	if(a.y==b.y) return a.x<b.x;
	return a.y<b.y;
}
int main(){
	
	r(n);r(m);
	register int i,R=0;
	for(i=1;i<=n;++i)
		r(a[i]);
	for(i=1;i<=m;++i)
		r(sec[i].x),r(sec[i].y),sec[i].id=i;
	sort(sec+1,sec+m+1,Cmp);
	for(i=1;i<=m;++i){
		while(R<sec[i].y){ 
			++R;
			if(!book[a[R]]) book[a[R]]=R,t.A(R,1);
			else t.A(book[a[R]],-1),book[a[R]]=R,t.A(R,1);
		}
		ans[sec[i].id]=t.G(sec[i].y)-t.G(sec[i].x-1);
	}
	for(i=1;i<=m;++i)
		w(ans[i]),putchar('\n');
	return 0;
}