//----AUTHOR:kkdrummer----/
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef    long long   ll;
typedef    long double   ld;
//typedef    unordered_set<ll>   usll;
//typedef    unordered_multiset<ll>   umsll;
typedef    multiset<ll>   msll;
typedef    set<ll>   sll;
typedef    vector<ll>   vll;
typedef    pair<ll,ll>   pll;
typedef    vector<pll>   vpll;
typedef    priority_queue<ll>   pqll;
typedef    vector<int>   vi;
typedef    set<int>   si;
typedef    multiset<int>   msi;
//typedef    unordered_multiset<int>   umsi;
//typedef    unordered_set<int>   usi;
typedef     pair<int,int>   pi;
typedef    vector<pi>   vpi;
typedef    set<pi>   spi;
typedef    priority_queue<int>   pqi;
typedef    tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>   ind_set;
typedef    tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>   ind_setll;
#define    in   insert
#define    fi   first
#define    se   second
#define    pb   push_back
#define    mp   make_pair
#define    be   begin
#define    en   end
#define    itr   iterator
#define io ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define    mo   1000000007
#define    inf  9223372036854775807
#define    ninf   -inf
#define    ima   2147483647
#define    imi   -ima
#define    oncnt    __builtin_popcount
#define    zerobegin   __builtin_clz
#define    zeroend   __builtin_ctz
#define    parity   __builtin_parity
#define    all(x)   x.be(),x.en()
#define    eps   1e-9
#define    coutd   cout<<setprecision(10)<<fixed
#define    mems(dp,x)   memset(dp,x,sizeof(dp))
const    ld   PI=3.1415926535897932384626433832792884197169399375105820974944;
inline ll modpow(ll x,ll n){if(n==0)return 1;if(n==1)return(x%mo);ll u=(modpow(x,n/2));u=(u*u)%mo;if(n%2!=0)u=(u*x%mo)%mo;return u;}
inline ll modinv(ll x){return modpow(x,mo-2);}
inline ll mmul(ll a,ll b){    if(a>=mo)a=a%mo;if(b>=mo)b=b%mo;if(a*b>=mo)return(a*b)%mo;return(a*b);}
inline ll madd(ll a, ll b){if(a>=mo)a=a%mo;if(b>=mo)b=b%mo;if(a+b>=mo)return(a+b)%mo;return(a+b);}
inline ll msub(ll a, ll b){if(a>=mo)a=a%mo;if(b>=mo)b=b%mo;return(((a-b)%mo+mo)%mo);}
inline ll mdiv(ll a,ll bb){if(a>=mo)a=a%mo;ll b=modinv(bb);if(b>=mo)b=b%mo;if(a*b>=mo)return(a*b)%mo;return(a*b);}
inline ll gcd(ll a,ll b){return __gcd(a,b);}
inline ll lcm(ll a,ll b){return ((a*b)/gcd(a,b));}

struct qu
{
int l,r,id;	
};
int z;
bool cool(qu a,qu b)
{
	if(a.l/z<b.l/z)
	return true;
	else if(a.l/z>b.l/z) return false;
	return (a.r<b.r);
}

int fr[5000001]={0};
int a[500001];
int main()
{
io
int testcases=1;//cin>>testcases;
while(testcases--)
{

int n,q;
cin>>n>>q;
z=sqrt(n);


for(int i=0;i<n;i++)
{
	cin>>a[i];
}





qu v[q];
for(int i=0;i<q;i++)
{
	int l,r;
	cin>>l>>r;
	l--;
	r--;
	qu ne;
	ne.l=l;
	ne.r=r;
	ne.id=i;
	v[i]=ne;
}

sort(v,v+q,cool);

fr[a[0]]++;
int st=0,e=0;
int ans[q];
int d=1;
for(int i=0;i<q;i++)
{
	int l=v[i].l;
	int r=v[i].r;
	
	while(st>l)
	{
		st--;
		fr[a[st]]++;
		if(fr[a[st]]==1)
		d++;
	
	}
	while(st<l)
	{
     fr[a[st]]--;
     if(fr[a[st]]==0)
     d--;
     st++;
	
	}
	while(e<r)
	{
		e++;
		fr[a[e]]++;
		if(fr[a[e]]==1)
		d++;
	}
	while(e>r)
	{
		fr[a[e]]--;
		if(fr[a[e]]==0)
		d--;
		e--;
	}
	ans[v[i].id]=d;
}

for(int i=0;i<q;i++)
cout<<ans[i]<<"\n";



}return 0;}


Measured memory_bytes: 15508