#include<bits/stdc++.h>
using namespace std;

# define C continue;
# define R return

# define D double
# define I insert
# define ll long long
# define ld long double

# define ull unsigned long long
# define ui unsigned int

# define pb push_back
# define pf push_front

# define vi vector < int >
# define vc vector < char >
# define vs vector < string >
# define vb vector < bool >
# define vd vector < D >
# define vll vector < ll >
# define vull vector < ull >
# define vld vector < ld >
# define PQ priority_queue

# define vvi vector < vector < int > >
# define vvb vector < vector < bool > >
# define vvc vector < vector < char > >
# define vvs vector < vs >
# define vvll vector < vector < ll > >
# define vvd vector < vector < D > >
# define vvld vector < vector < ld > >

# define all(v) (v).begin() , (v).end()
# define allrev(v) (v).rbegin() , (v).rend()
# define allcomp(v) v.begin() , v.end() , comp
# define allrevcomp(v) v.rbegin() , v.rend() , comp

# define pii pair < int , int >
# define pll pair < ll , ll >
# define pld pair < ld , ld >
# define pDD pair < D , D >

# define vpld vector < pld >
# define vpii vector < pii >
# define vpll vector < pll >
# define vpDD vector < pDD >

# define vvpii vector < vector < pii > >
# define F first
# define S second
# define mp make_pair

# define dist(a,b,p,q) sqrt((p-a)*(p-a) + (q-b)*(q-b))

# define pp(n) printf("%.10Lf",n);
# define line cout<<"\n";
# define fast ios_base::sync_with_stdio(false) ; cin.tie(0) ; cout.tie(0);

string vow = "aeiou";
int month[] = {-1, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

const int dxhorse[] = {-2, -2, -1, -1, 1, 1, 2, 2};
const int dyhorse[] = {1, -1, 2, -2, 2, -2, 1, -1};

const int dx[] = { -1 , 0 , 1 , 0 } ;
const int dy[] = { 0 , 1 , 0 , -1 } ;

const ld pie = 3.1415926535897932384626 ;
const ll mod = 1e9 + 7 ;

/// Tip : If a and b are positive integers ; we may say - ceil (a/b) = 1 + floor ( (a-1)/b ) .

const int N = 5e5 + 10 ;

int v[N] ;
vvi qry ;

int n , q ;

void read ()
{
    cin >> n >> q ;

    for ( int i=0 ; i < n ; i ++ )
        cin >> v[i] ;

    qry.resize ( q ) ;

    for ( int i=0 ; i < q ; i ++ )
    {
        int l , r ;
        cin >> l >> r ;

        l -- ; r -- ;

        qry[i] = { l , r , i } ;
    }
}

int z ;

bool comp ( const vi &a , const vi &b )
{
    if ( a[0] / z != b[0] / z )
        return a < b ;

    if ( ((a[0] / z)&1) )
        return a[1] > b[1] ;

    return a[1] < b[1] ;
}

int cnt = 0 ;
int h[N] ;

void add ( const int &indx )
{
    int val = v[indx] ;

    h[val] ++ ;
    if ( h[val] == 1 ) cnt ++ ;
}

void del ( const int &indx )
{
    int val = v[indx] ;

    h[val] -- ;
    if ( h[val] == 0 ) cnt -- ;
}

void solve ( int test_case )
{
    read () ;

    z = sqrt ( n ) ;
    if ( z * z < n )
        z ++ ;

    sort ( allcomp ( qry ) ) ;

    int i = 0 , j = -1 ;
    vi ans ( q ) ;

    for ( int indx = 0 ; indx < q ; indx ++ )
    {
        int l = qry[indx][0] , r = qry[indx][1] ;

//        cout << "l and r : " << l + 1 << " " << r + 1 ; line ;

        while ( j < r )
            add ( ++j ) ;

        while ( j > r )
            del ( j -- ) ;

        while ( i < l )
            del ( i ++ ) ;

        while ( i > l )
            add ( --i ) ;

//        cout << "i : " << i + 1 << " and j : " << j + 1 << " and cnt : " << cnt ; line ;

        ans[qry[indx][2]] = cnt ;
    }

    for ( auto &i : ans )
        cout << i , line ;

//    line ;
}

int main()
{fast
    int t = 1;
    // cin >> t;

    for ( int i = 1 ; i <= t ; i ++ )
    {
        solve ( i ) ;
    }

    return 0;
}


Measured memory_bytes: 37000