#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define N 100005
ll block=1300;
void fastio()
{
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
}
struct Query
{
	ll l;
	ll r;
	ll i;
};
Query Q[500005];
ll ar[500005];
ll check[500005];
ll ans[500005];
ll cnt=0;
bool comp(Query a,Query b){
    if(a.l/block!=b.l/block)
        return a.l<b.l;
    return a.l/block % 2 ? a.r<b.r:a.r>b.r;
}
void add(ll pos)
{
	check[ar[pos]]++;
	if(check[ar[pos]]==1)
	cnt++;
}
void remove(ll pos)
{
	check[ar[pos]]--;
	if(check[ar[pos]]==0)
	cnt--;
}
int main() {
	fastio();
	ll n,x,y,m;
	cin>>n>>m;
	for(int i=0;i<n;i++)
	cin>>ar[i];
	
	for(int i=0;i<m;i++){
		cin>>x>>y;
		Q[i].i=i;
		Q[i].l=--x;
		Q[i].r=--y;
	}

	sort(Q,Q+m,comp);
	ll cur_l=0;
	ll cur_r=-1;
	for(int i=0;i<m;i++)
	{
	ll L=Q[i].l;
	ll R=Q[i].r;
	while(cur_l>L)
	add(cur_l-1),cur_l--;
	
	while(cur_r<R)
	add(cur_r+1),cur_r++;
	
	while(cur_l<L)
	remove(cur_l),cur_l++;
	
	while(cur_r>R)
	remove(cur_r),cur_r--;
	
	ans[Q[i].i]=cnt;
	}
	for(int i=0;i<m;i++)
	cout<<ans[i]<<'\n';

	
	return 0;
}