#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int N,Q;
const int W=700;
int c[5<<17];
int ans[5<<17];
int cnt[5<<17];
int main()
{
	cin>>N>>Q;
	for(int i=0;i<N;i++)cin>>c[i];
	vector<vector<pair<int,pair<int,int> > > >qs((N+W-1)/W);
	for(int i=0;i<Q;i++)
	{
		int l,r;cin>>l>>r;
		l--;
		qs[l/W].push_back(make_pair(r,make_pair(l,i)));
	}
	int L=0,R=0;
	int all=0;
	for(int i=0;i<qs.size();i++)
	{
		while(L<i*W&&L<N)
		{
			if(!--cnt[c[L++]])all--;
		}
		while(i*W<R)
		{
			if(!--cnt[c[--R]])all--;
		}
		sort(qs[i].begin(),qs[i].end());
		for(int j=0;j<qs[i].size();j++)
		{
			int r=qs[i][j].first;
			while(R<r)
			{
				if(!cnt[c[R++]]++)all++;
			}
			int l=qs[i][j].second.first;
			while(L<l)
			{
				if(!--cnt[c[L++]])all--;
			}
			while(L>l)
			{
				if(!cnt[c[--L]]++)all++;
			}
			ans[qs[i][j].second.second]=all;
		}
	}
	for(int i=0;i<Q;i++)cout<<ans[i]<<endl;
}