#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define fastIO ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define int long long int
#define pb push_back
#define ff first
#define ss second
#define all(v) (v).begin(), (v).end()
#define mod (int)(998244353)
#define PI 3.14159265358979323846264338327950L
// ------------------ Debugging ------------------
#define trace(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args);cout << endl; }
void err(istream_iterator<string> it) {}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
    cerr << "[ " << *it << " = " << a << " ] ";
    err(++it, args...);
}
template <typename Tk, typename Tv> ostream& operator<<(ostream& os, const pair<Tk, Tv> &p){os << "{" << p.first << ',' << p.second << "}";return os;}
template <typename T> ostream& operator<<(ostream& os, const vector<T> &p){os << "[ "; for (T x: p) os << x << " "; os << "]" << endl; return os;}
template <typename T> ostream& operator<<(ostream& os, const set<T> &p){os << "{ "; for (T x: p) os << x << " "; os << "}" << endl; return os;}
template <typename Tk, typename Tv> ostream& operator<<(ostream& os, const map<Tk, Tv> &p){os << "{ "; for (pair<Tk, Tv> x: p) os << x << " "; os << "}" << endl; return os;}
// -----------------------------------------------

class BIT{
public:
    vector<int> bit;
    int N;
    /**
     * Creating tree is like updating Fenwick tree for every value in array
     */
    // BIT(int arr[], int n){ // set the argument accordingly to the array type
    //     N = n;
    //     bit.assign(N+1, 0);
    //     for (int i = 1; i <= N; i++) {
    //         updateBIT(arr[i-1], i);
    //     }
    // }
    BIT(int n) {
        N = n + 10;
        bit.assign(N, 0);
    }
    /**
     * Start from index+1 if you updating index in original array. Keep adding this value 
     * for next node till you reach outside range of tree
     */
    void updateBIT(int val, int idx) {
        while (idx > 0 && idx < N+1) {
            bit[idx] += val;
            idx = getNext(idx);
        }
    }

    void update(int val, int idx){
        int diff = val - bit[idx];
        updateBIT(diff, idx);
    }

    /**
     * To get next
     * 1) 2's complement of get minus of index
     * 2) AND this with index
     * 3) Add it to index
     */
    int getNext(int idx) {
        return idx + (idx & -idx);
    }

    /**
     * Start from index+1 if you want prefix sum 0 to index. Keep adding value
     * till you reach 0
     */
    int getSum(int idx) {
        idx++;
        int sum = 0;
        while (idx > 0) {
            sum += bit[idx];
            idx = getParent(idx);
        }
        return sum;
    }
    /**
     * To get parent
     * 1) 2's complement to get minus of index
     * 2) AND this with index
     * 3) Subtract that from index
     */
    int getParent(int idx) {
        return idx - (idx & -idx);
    }

};

struct Query {
    int l, r, idx;
};

signed main(){

    fastIO

    int n, q;
    cin >> n >> q;

    int c[n];
    for (int &i : c) {
        cin >> i;
    }

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

        qry[i].l = l;
        qry[i].r = r;
        qry[i].idx = i;
    }

    sort(qry, qry + q, [&](Query x, Query y) {
        return x.r < y.r;
    });
    
    // for (Query val : qry) {
    //     trace(val.l, val.r, val.idx);
    // }
    BIT bit(n);
    vector<int> ans(q), last_seen(n+1, -1);
    int qcnt = 0;

    for (int i = 1; i <= n; i++) {
        // trace(i, c[i-1], last_seen[c[i-1]]);
        if (last_seen[c[i-1]] != -1) {
            bit.updateBIT(-1, last_seen[c[i-1]]);
        }
        last_seen[c[i-1]] = i;
        // trace(i, last_seen[c[i-1]]);
        bit.updateBIT(1, i);
        // trace(i, last_seen[c[i-1]]);
        while (qcnt < q && qry[qcnt].r == i) {
            ans[qry[qcnt].idx] = bit.getSum(qry[qcnt].r - 1) - bit.getSum(qry[qcnt].l - 2);
            qcnt++;
        }
    }

    for (int val : ans) {
        cout << val << endl;
    }

    return 0;
}

Measured memory_bytes: 31092