#include <cstdio>
#include <cstdlib>
#include <iomanip>
#include <iostream>
#include <list> 
#include<algorithm>
#include<cmath>
#include<map>
#include<vector>
#include<string>
#include<fstream>
#include<set>
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define forl(i,a,n) for(int i=a;i<n;i++)
#define rfor(i,n,a) for(int i=n;i>=a;i--)
#define ll long long
#define ull unsigned long long
#define ld long double
#define pb push_back
#define ld long double
#define vi vector<int>
#define vll vector<long long>
#define pi pair<int,int>
#define pll pair<long long,long long>
#define mp make_pair
#define B begin()
#define E end()
#define S size()
#define m9 1000000007
using namespace std;
 
 

 
ll gcd(ll x,ll y)
{
    if(x==0) return y;
    return gcd(y%x,x);
}
 
/*
ll gcdextended(ll a, ll b, ll *x, ll *y) 
{ 
    if (a == 0) 
    { 
        *x = 0, *y = 1; 
        return b; 
    } 
  
    ll x1, y1; 
    int gcd = gcdextended(b%a, a, &x1, &y1); 
   
    *x = y1 - (b/a) * x1; 
    *y = x1; 
  
    return gcd; 
}
 
 
///RELATIVE COPRIME
ll modinverse(ll a, ll m) 
{ 
    ll x, y; 
   ll g = gcdextended(a, m, &x, &y); 
    if (g != 1) 
return -1;
    else
    { 
        ll res = (x%m + m) % m; 
        return res;  
    } 
} 
  */
ll powmod(ll x, ll y, ll m) 
{ 
    if (y == 0) 
        return 1; 
    ll p = powmod(x, y/2, m) % m; 
    p = (p * p) % m; 
    return (y%2 == 0)? p : (x * p) % m; 
} 
///M IS PRIME
ll modif(ll x,ll m){
return(powmod(x,m-2,m));
 
}
 
 
 
#define p0(a) cout << a << " "
#define p1(a) cout << a << endl
#define p2(a, b) cout << a << " " << b << endl
#define p3(a, b, c) cout << a << " " << b << " " << c << endl
#define p4(a, b, c, d) cout << a << " " << b << " " << c << " " << d << endl
#define pin(a) for(auto x:a)cout<<x<<" ";cout<<endl
#define fck(a) cout<<a;exit(0)
#define vvll vector<vector<ll> >
#define A(b) b.begin(),b.end()
#define vpi std::vector<pll>
#include <array>
#include <stack>
//include<bits/stdc++.h>
 
 
bool fa(vll &x,vll &y){return x[0]<y[0];}
bool fa1(vll &x,vll &y){return x[1]<y[1];}
bool f1(pll &x,pll &y){return x.second>y.second;}
bool f2(pll &x,pll &y){
    return x.first>y.first;
}
 
 
bool f3(ll &x,ll &y){
    return x>y; 
    }

ll te;
ll n,qq;
ll block=800;
bool meow(array<ll,3> x,array <ll,3> &y){
    
    if(x[0]/block!=y[0]/block){
        return x[0]/block<y[0]/block;
    }
    else {
        return x[1]<y[1];
    }
}




const ll maxn=5e5+2;
ll d[maxn];
ll b[maxn];
ll cnt=0;
void add(ll pos){
    d[b[pos]]++;
    if(d[b[pos]]==1)cnt++;
}
void remove(ll pos){
    d[b[pos]]--;
    if(d[b[pos]]==0)cnt--;
}


int main()
{ fastio;
//freopen("test_input (1).xt", "r", stdin); 
//freopen("output.txt", "w", stdout);
cin>>n>>qq;
forl(i,0,n)d[i]=0;
forl(i,0,n)cin>>b[i];
std::vector<array<ll,3> > q(qq);
forl(i,0,qq){
cin>>q[i][0]>>q[i][1];
q[i][0]--;q[i][1]--;
q[i][2]=i;
}
ll ans[qq];

forl(i,0,qq)ans[i]=-1;


sort(q.B,q.E,meow);
// for(auto x:q){
//     p2(x[0]+1,x[1]+1);
// }
ll ml=0,mr=-1;
forl(i,0,qq){
    ll l=q[i][0],r=q[i][1];
    while(ml>l){
        ml--;
        add(ml);
    }
    while(mr<r){
        mr++;
        add(mr);
    }
    while(ml<l){
        remove(ml);ml++;
    }
    while(mr>r){
        remove(mr);mr--;
    }
    ans[q[i][2]]=cnt;
}
for(auto x:ans){
    cout<<x<<"\n";
}



return 0;
}




  










Measured memory_bytes: 27188