#include<bits/stdc++.h>
using namespace std;
const int N=500005;
int n,q,a[N],l[N],r[N],b[N],c[N],ans[N];
vector<pair<int,int>>x[N];
void add(int x,int v)
{
	for(int i=x;i<=n;i+=i&(-i))
		b[i]+=v;
}
int sum(int x)
{
	int v=0;
	for(int i=x;i;i-=i&(-i))
		v+=b[i];
	return v;
}
int main()
{
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	for(int i=1;i<=q;i++)
	{
		scanf("%d%d",&l[i],&r[i]);
		x[r[i]].emplace_back(l[i],i);
	}
	for(int i=1;i<=n;i++)
	{
		if(c[a[i]])
			add(c[a[i]],-1);
		c[a[i]]=i;
		add(i,1);
		for(auto zh:x[i])
			ans[zh.second]=sum(i)-sum(zh.first-1);
	}
	for(int i=1;i<=q;i++)
		printf("%d\n",ans[i]);
	return 0;
}