#include <cstdio>
#include <algorithm>
#define pi std::pair<int,int>
const int maxN = 5e5+9;
struct Query{
	int l,r,i;
}query[maxN];
int last[maxN],arr[maxN],BIT[maxN],ans[maxN];
void update(int index,int val,int n){
	while(index<=n){
		BIT[index]+=val;
		index+=(index&-index);
	}
}
int ask(int index){
	int ret=0;
	while(index>0){
		ret+=BIT[index];
		index-=(index&-index);
	}
	return ret;
}
int main(){
	int n,q;
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n;i++)scanf("%d",&arr[i]);
	for(int i=0;i<q;i++){scanf("%d%d",&query[i].l,&query[i].r);query[i].i=i;}
	std::sort(query,query+q,[](Query &q1,Query &q2){ return (q1.r<q2.r);});
	int r=1;
	for(int i=0;i<q;i++){
		while(r<=query[i].r){
			if(last[arr[r]])update(last[arr[r]],-1,n);
			update(r,1,n);last[arr[r]]=r;r++;
		}
		ans[query[i].i] = ask(query[i].r) - ask(query[i].l-1);
	}
	
	for(int i=0;i<q;i++)printf("%d\n",ans[i]);
}
