#include <iostream>
#include <math.h>
#include <cstdlib>
#include <algorithm>
#include <cstdlib>
#include <string>
#include <stdio.h>
#include <cstdio>
#include <vector>
#include <cstring>
#include <bits/stdc++.h>

using namespace std;

pair <int,int> T_z[500100], T_or[500100];
int T_l[500100], T_najb[500100], tree[1048576], sts[500100];

bool comparison(const pair<int,int> &a,const pair<int,int> &b){
    return ((a.first>b.first)||((a.first==b.first)&&(a.second>b.second)));
}
void wstaw(int x, int indx, int drz[])
{
    drz[indx]=x;
    while (indx!=1)
    {
        indx/=2; drz[indx]=drz[indx*2]+drz[indx*2+1];
    }
}
int suma_prz(int l, int p, int drz[])
{
    if (l==p) return drz[l];
    if (l/2==p/2) return drz[l/2];
    int res=drz[l]+drz[p];
    if (l%2==0) res+=drz[l+1];
    if (p%2==1) res+=drz[p-1];
    while (l/2/2!=p/2/2)
    {
        l/=2; p/=2;
        if (l%2==0) res+=drz[l+1];
        if (p%2==1) res+=drz[p-1];
    }
    return res;
}
int su_bin(int p1, int p2, int poc, int kon,  pair <int,int> T_wys[])
{
    int res, sr;
    while (poc<=kon)
    {
    sr=(poc+kon)/2;
    if (T_wys[sr].first<p1) {res=sr; kon=sr-1; continue;}
    if ((T_wys[sr].first==p1)&&(T_wys[sr].second<=p2)) {res=sr; kon=sr-1; continue;}
    poc=sr+1;
    }
    return res;
}

int main()
{
    ios_base::sync_with_stdio(0);
    int n, q; cin>>n>>q;
    for (int i=0;i<n;i++) cin>>T_l[i];
    for (int i=0;i<q;i++)
    {
    cin>>T_z[i].first>>T_z[i].second;
    T_or[i].first=T_z[i].first; T_or[i].second=T_z[i].second;
    }
    sort(T_z, T_z+q, comparison);
    int pot;
    for (int i=1;;i=i*2)
    {
        if (i>=n) { pot=i; break; }
    }
    int kt_q=0; bool prz=false;
    for (int i=n-1;i>=0;i--)
    {
       if (prz) break;
       if (T_najb[T_l[i]]!=0) wstaw(0, pot+T_najb[T_l[i]], tree);
       wstaw(1, pot+i, tree);
       T_najb[T_l[i]]=i;
       while (T_z[kt_q].first==i+1)
       {
           sts[kt_q]=suma_prz(T_z[kt_q].first+pot-1, T_z[kt_q].second+pot-1, tree);
           kt_q++;
           if (kt_q==q)  {prz=true; break;}
       }
    }
    for (int i=0;i<kt_q;i++)
    {
        cout<<sts[su_bin(T_or[i].first,T_or[i].second, 0, kt_q, T_z)]<<"\n";
    }

}

#include <iostream>
#include <functional>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <set>
#include <queue>
#include <map>
#include <iomanip>
#include <complex>
#include <random>
#include <bitset>
#include <list>
// #include <prettyprint.hpp>
using namespace std;
#define repi(i,n) for(int i=0;i<n;++i)
#define rep(i,n) for(ll i=0;i<n;++i)
#define repinvi(i,n) for(int i=n-1;i>=0;--i)
#define sll(n) scanf("%lld", &n);
#define sii(n) scanf("%d", &n);
#define slf(n) scanf("%lf", &n);
#define pll pair<ll,ll>
#define pii pair<int,int>
#define psi pair<si,si>
typedef long long ll;
typedef double lf;
typedef short int si;


template<typename T>
class BIT{
    public:
        vector<T> x_list;
        ll n;

        BIT(ll n=1, T fill_value=0): n(n){
            x_list.resize(n+1);
            fill(x_list.begin(), x_list.end(), fill_value);
        }

        void add(ll idx, T v){
            for(ll x=idx; x<= n;x += (x & -x)){
                x_list[x] += v;
            }
        }

        ll get_sum(ll idx){
            T v = 0;
            for(ll x=idx;x>0;x-=(x & -x)){
                v += x_list[x];
            }
            return v;
        }
};

void Main(){
    ll N, Q, c, l, r;
    cin >> N >> Q;
    vector<ll> as(N);
    vector<vector<pll>> qs(N);
    // vector<pll> qs_org(Q);
    vector<ll> ans(Q);
    rep(i, N){
        cin >> as[i];
    }

    rep(i, Q){
        cin >> l >> r;
        -- l;
        -- r;
        qs[r].emplace_back(l, i);
        // qs_org[i] = make_pair(r, l);
    }

    // sort(qs.begin(), qs.end());

    map<ll,ll> color_best;
    // ll now_r = qs[0].first;

    BIT<ll> bitree(N, 0);

    rep(i, N){
        // if(color_best[as[i]]<=i){
            // continue;
        // }
        if(color_best.find(as[i])!=color_best.end() ){
            if(color_best[as[i]]<i){
                bitree.add(color_best[as[i]]+1, -1);
                bitree.add(i+1, 1);
                color_best[as[i]] = i;
            }
        }else{
            bitree.add(i+1, 1);
            color_best[as[i]] = i;
        }
        if(qs[i].size() == 0){
            continue;
        }
        for(auto q:qs[i]){
            ans[q.second] = bitree.get_sum(i+1) - bitree.get_sum(q.first);
        }
    }
    rep(i, Q){
        cout << ans[i] <<endl;
    }

}

int main(){
    Main();
}