// Original C++ solution (slower):
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;



#define IOS ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);

#define pb push_back

#define mp make_pair

#define ff first

#define ss second

#define I insert

#define endl '\n'

#define all(x) x.begin(), x.end()



#include <ext/pb_ds/assoc_container.hpp>

#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;

template<class T> using oset=tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

 

using vvll = vector< vector<ll> >;

using vll = vector<ll> ;

using vb = vector<bool> ;

using pll = pair<ll, ll> ;



const ll maxs = 1e6+5;

const ll lmaxs = 20;

ll mod = 1e9+7;

ll oo = 1e15;



void pre(){



    



}

int n;

int p[maxs];

int a[maxs];

int bit[maxs];



void add(ll ind,ll val){

    while(ind<=n){

        bit[ind] += val;

        ind += ind&-ind;

    }

}



int get(int ind){

    ll sum=0;

    while(ind){

        sum += bit[ind];

        ind -= ind&-ind;

    }

    return sum;

}





void solve(){



    int m;

    cin>>n>>m;

    int id=1;

    map<int,int> mp;

    memset(p,-1,sizeof p);

    for(int i=1;i<=n;i++){

        cin>>a[i];

        if(mp.find(a[i]) == mp.end()){

            mp[a[i]] = id++;

        }

    }

    for(int i=1;i<=n;i++){

        a[i] = mp[a[i]];

    }

    // for(ll i=1;i<n+1;i++)   

    //     cout << a[i] << " ";

    // cout << endl;

    pair<pair<int,int>,int> q[m];

    int ANS[m];

    for(int i=0;i<m;i++){

        cin>>q[i].ff.ff>>q[i].ff.ss;

        q[i].ss = i;

    }

    sort(q,q+m,[&](pair<pair<int,int>,int> a,pair<pair<int,int>,int> b)->bool{

        return a.ff.ss < b.ff.ss;

    });

    ll ptr=0;

    for(int i=1;i<=n;i++){

        if(p[a[i]] != -1)

            add(p[a[i]],-1);

        p[a[i]] = i;

        add(i,1);



        while(ptr < m and q[ptr].ff.ss == i){

            int x = q[ptr].ff.ff;

            int ind = q[ptr].ss;

            int res = get(i) - get(x-1);

            ANS[ind] = res;

            ptr++;

        }

    }



    for(int i=0;i<m;i++){

        cout << ANS[i] << endl;

        //printf("%d\n",ANS[i]);

    }









}



int main(){



    IOS;

    pre();

    ll T = 1;

    //cin>>T;

    while(T--){

        solve();   

    }

    return 0;

}

// Optimized solution to the same problem (faster):
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;



#include <ext/pb_ds/assoc_container.hpp>

#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;

template<class T> using oset=tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

 

using vvll = vector< vector<ll> >;

using vll = vector<ll> ;

using vb = vector<bool> ;

using pll = pair<ll, ll> ;



#define IOS ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);

#define pb push_back

#define mp make_pair

#define ff first

#define ss second

#define I insert

#define ar array

#define endl '\n'

#define all(x) x.begin(), x.end()

#define sz(x) ((long long)x.size())



const ll maxs = 1e6+5;

const ll lmaxs = 20;

ll mod = 1e9+7;

ll oo = 1e15;



ll fast(ll x,ll y){

    ll res=1;

    while(y){

        if(y&1)

            res = (res*x)%mod;

        x = (x*x)%mod;

        y >>= 1;

    }

    return res;

}



ll inv(ll n){

    return fast(n,mod-2);

}





void pre(){





}



struct  DATA{

    int l,r,i;

};  

int bit[maxs];

int n,q;



void add(int ind,int val){

    while(ind <= n){

        bit[ind] += val;

        ind += ind&-ind;

    }

}



int get(int ind){

    int sum=0;

    while(ind){

        sum += bit[ind];

        ind -= ind&-ind;

    }

    return sum;

}



void solve(){    



    cin >> n >> q;

    vector<int> a(n+1);

    for(int i=1;i<=n;i++){

        cin >> a[i];

    }

    DATA AllQueries[q+1];

    for(int i=1;i<=q;i++){

        cin >> AllQueries[i].l >> AllQueries[i].r;

        AllQueries[i].i = i;

    }

    vector<int> ans(q+1,0);

    sort(AllQueries+1,AllQueries+q+1,[&](DATA A,DATA B)->bool{

        return A.r < B.r;

    });



    int ptr_query=1;

    map<int,int> prev;

    for(int i=1;i<=n;i++){

        if(prev.count(a[i])){

            add(prev[a[i]],-1);

        }

        add(i,1);



        while(ptr_query <= q and i == AllQueries[ptr_query].r){

            int l = AllQueries[ptr_query].l;

            int r = i;

            int ind = AllQueries[ptr_query].i;

            int cur_ans = get(r) - get(l-1);

            ans[ind] = cur_ans;

            ptr_query++;

        }

        prev[a[i]] = i;

    }



    for(int i=1;i<=q;i++){

        cout << ans[i] << endl;

    }



}



int main(){

   

    IOS;

    pre();

    ll T = 1;

    //cin >> T;

    while(T--){

        solve();   

    }

    return 0;

}

// Fastest known solution for this problem: