include

include

include

include

include

include

typedef long long LL;
typedef unsigned long long ULL;
using namespace FastIo;
#define NUMBER1 500000
#define P(A) A=-~A
#define fione_i(begin,end) for(register int i=begin;i<=end;P(i))
int n,m,fk,cnt[NUMBER1+5],a[NUMBER1+5],b[NUMBER1+5],ans[NUMBER1+5],sum(0);
struct ASK{
	int l,r,id;
	bool operator<(const ASK &A)const{return l/fk==A.l/fk?r<A.r:l<A.l;}
}ask[NUMBER1+5];
inline void add(int k){
	P(cnt[k]);
	if(cnt[k]==2)P(sum);
	else if(cnt[k]==3)--sum;
}
inline void del(int k){
	--cnt[k];
	if(cnt[k]==2)P(sum);
	else if(cnt[k]==1)--sum;
}
signed main(){
	int l(1),r(0),m1;
	qrw.read(n);
	qrw.read(m);
	fk=sqrt(n);
	fione_i(1,n){
		qrw.read(a[i]);
		b[i]=a[i];
	}
	std::sort(b+1,b+1+n);
	m1=std::unique(b+1,b+1+n)-b;
	fione_i(1,n)a[i]=std::lower_bound(b+1,b+1+m1,a[i])-b;
	fione_i(1,m){
		qrw.read(ask[i].l);
		qrw.read(ask[i].r);
		ask[i].id=i;
	}
	std::sort(ask+1,ask+1+m);
	fione_i(1,m){
		while(l<ask[i].l)del(a[l++]);
		while(l>ask[i].l)add(a[--l]);
		while(r>ask[i].r)del(a[r--]);
		while(r<ask[i].r)add(a[++r]);
		ans[ask[i].id]=sum;
	}
	fione_i(1,m)qrw.write(ans[i]);
	fsh;
    exit(0);
    return 0;
}