#include <bits/stdc++.h>

#define MAXN 500000

using namespace std;
using pi = pair<int, int>;

// t: array pra armazenar a seg tree
int t[4*MAXN];

// função que combina os resultados de dois nós da seg tree
int combine(int a, int b) {
    return a+b;
}

// a: array que vai ser usado pra construir a seg tree
// v: índice do vértice atual (na árvore)
// l: início do intervalo (índice do vetor)
// r: fim do intervalo (índice do vetor)
void build(vector<int> &a, int v, int l, int r) {
    if (l == r) {
        // l == r -> estamos em uma folha, basta colocar o valor da folha
        t[v] = a[l];
        return;
    }

    // m: meio do array -> para separar em dois intervalos [l, m] e [m+1, r]
    int m = (l+r)/2;

    // chamada recursiva para os nós-filhos
    build(a, 2*v,   l,   m);
    build(a, 2*v+1, m+1, r);

    // combina o resultado dos nós-filhos no nó atual
    t[v] = combine(t[2*v], t[2*v+1]);
}

// v: índice do vértice atual (na árvore)
// l: início do intervalo (índice do vetor)
// r: fim do intervalo (índice do vetor)
// ql: início do intervalo da query
// qr: fim do intervalo da query
int query(int v, int l, int r, int ql, int qr) {
    // nesse caso o intervalo atual é disjunto do da query
    if (ql > r || qr < l)
        return 0;
    // nesse caso o intervalo atual está inteiramente contido no da query
    if (l >= ql && r <= qr)
        return t[v];

    // m: meio do array -> para separar em dois intervalos [l, m] e [m+1, r]
    int m = (l+r)/2, queryL, queryR;

    // chamada recursiva para os nós-filhos
    queryL = query(2*v,   l,   m, ql, qr);
    queryR = query(2*v+1, m+1, r, ql, qr);

    // combina o resultado dos nós-filhos no nó atual
    return combine(queryL, queryR);
}

// v: índice do vértice atual (na árvore)
// l: início do intervalo (índice do vetor)
// r: fim do intervalo (índice do vetor)
// pos: posição do nó que deve ser atualizado (índice do vetor)
// val: valor novo desse nó
void update(int v, int l, int r, int pos, int val) {
    // l == r -> está em uma folha -> atualiza o valor
    if (l == r) {
        t[v] = val;
        return;
    } 

    int m = (l+r)/2;

    // se o nó que deve ser atualizado está no intervalo à esquerda, desce para a esquerda
    if (pos <= m)
        update(2*v,   l,   m, pos, val);
    // caso contrário, desce para a direita
    else
        update(2*v+1, m+1, r, pos, val);

    // combina os resultados dos filhos para atualizar o resultado do pai
    t[v] = combine(t[2*v], t[2*v+1]);
}

void solve() {
    int n, q;
    cin >> n >> q;

    vector<int> c(n);
    vector<int> inc(n, 0);
    vector<int> lastUpdatePos(n, -1);

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

    vector<pi> queries(q), s_queries(q);
    map<pi, int> ans; 
    for (int i = 0; i < q; ++i) {
        int l, r;
        cin >> l >> r;

        queries[i] = make_pair(l, r);

        --l; --r;
        s_queries[i] = make_pair(r, l);
    }

    sort(s_queries.begin(), s_queries.end());

    build(inc, 1, 0, n-1);

    int i = 0;
    for (auto &qry : s_queries) {
        while (i <= qry.first) {
            int lastUpdt = lastUpdatePos[c[i]-1];

            if (lastUpdt != -1) {
                inc[lastUpdt] = 0;
                lastUpdatePos[c[i]-1] = i;
                update(1, 0, n-1, lastUpdt, 0);
            }

            inc[i] = 1;
            lastUpdatePos[c[i]-1] = i;
            update(1, 0, n-1, i, 1);

            ++i;
        }
        pi ansqry = make_pair(qry.second+1, qry.first+1);
        ans[ansqry] = query(1, 0, n-1, qry.second, qry.first);
    }

    for (auto &qry : queries) {
        cout << ans[qry] << endl;
    }

}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif

    int t = 1;
    // cin >> t;

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

    return 0;
}


Measured memory_bytes: 52812