#include <bits/stdc++.h>
#define int long long
using namespace std;
const int TOP=5e5+5;
struct wod
{
	int num,l,r;
};
int n,m;
int a[TOP];
wod t[TOP];
int c[TOP];//树状数组
int biaoji[TOP];
int ans[TOP];
int lowbit(int x)
{
	return x&-x;
}
void add(int x,int y)
{
	int f;
	for(f=x;f<=n;f+=lowbit(f))
		c[f]+=y;
	return ;
}
int ask(int x)
{
	if(x<=0)
		return 0;
	int f,k;
	int ans=0;
	for(f=x;f;f-=lowbit(f))
		ans+=c[f];
	return ans;
}
bool cmp(wod one,wod tow)
{
	return one.r<tow.r;
}
signed main()
{
	int f,k;
	//输入
	cin>>n>>m;
	for(f=1;f<=n;f++)
		cin>>a[f];
	for(f=1;f<=m;f++)
	{
		cin>>t[f].l>>t[f].r;
		t[f].num=f;
	}
	
	sort(t+1,t+1+m,cmp);
	for(f=1,k=1;f<=n;f++)
	{
		if(biaoji[a[f]])
			add(biaoji[a[f]],-1);
		biaoji[a[f]]=f;
		add(f,1);
		while(k<=m&&t[k].r<=f)
		{
			ans[t[k].num]=ask(t[k].r)-ask(t[k].l-1);
			k++;
		}
	}
	
	for(f=1;f<=m;f++)
		cout<<ans[f]<<endl;
	return 0;
}