/***
 ** " Dream is not that which you see while sleeping it is something that does not let you sleep "
 **     -- A.P.J Abdul Kalam
***/

/**
  *  Author: dhruv_gheewala
  *  Problem: Range Set Query
  *  Date:   04.08.2020
  *  Time:   10:26:47
**/

#if __has_include("debug.h")
    #include "debug.h"
#else
    #include<bits/stdc++.h>
    using namespace std;
    
    #define fundri 108
    #define debug(...) 1729
#endif

#define int int64_t
typedef pair<int, int> pii;
typedef vector<int> vi;

const bool testcases = false;
#define ff first
#define ss second
#define endl '\n'
#define all(s) s.begin(), s.end()

// if vector isn't soted then it will remove consecutive same elements
#define make_unique(vec) vec.erase(unique(all(vec)), vec.end())
#define test int TC = 1;if(testcases)cin >> TC;for(int tc = 1 ; tc <= TC ; tc++)solve(), fundri
#define sort_by(cont,expr) sort(all(cont),[&](const auto &lhs,const auto &rhs){return expr;})

int seed; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
inline int rnd(int l = 0, int r = INT_MAX) {return uniform_int_distribution<int>(l, r)(rng);}

inline bool in_range(int a, int l, int r) {return (a >= l && a <= r);}
template<typename H, typename ...T>void inp(H &head) {cin >> head;}
template<typename H, typename ...T>void inp(H &head, T &...tail) {cin >> head;inp(tail...);}
template<typename T>bool isPrime(T n) {for(T i = 2; i * i <= n; i++)if(n % i == 0)return false; return n >= 2;}
template<typename T>inline istream &operator >>(istream &in, vector<T> &a) {for(T &x : a)in >> x; return in;}
template<typename T, typename U>inline istream &operator >>(istream &in, pair<T, U> &a) {in >> a.ff >> a.ss; return in;}

void solve();
void fast_io();

int32_t main(int32_t argc, char **argv)
{
    fast_io();
    test;
    return 0;
}

vi freq, c;
struct query {
    int l, r, id, eval;
    // define variables
    
    query() {}
    query(int _l, int _r, int _id) : l(_l), r(_r), id(_id) {calcEval();}
    inline void calcEval() {eval = giveOrder(l, r, 21, 0);}
    inline friend bool operator <(const query &lhs, const query &rhs) {return lhs.eval < rhs.eval;}

    inline int64_t giveOrder(int x, int y, int pow, int rotate)
    {
        if(pow == 0) return 0;
        int hpow = 1 << (pow - 1);
        int seg = x < hpow ? y < hpow ? 0 : 3 : y < hpow ? 1 : 2;
        seg = (seg + rotate) & 3;
        const static int rotateDelta[4] = {3, 0, 0, 1};
        int nx = x & (x ^ hpow);
        int ny = y & (y ^ hpow);
        int nrot = (rotate + rotateDelta[seg]) & 3;
        int64_t subSquareSize = 1LL << ((pow - 1) << 1);
        int64_t ans = seg * subSquareSize;
        int64_t add = giveOrder(nx, ny, pow - 1, nrot);
        ans += (seg == 1 || seg == 2) ? add : subSquareSize - add - 1;
        return ans;
    }
};

void mo(vector<query> &q)
{
    /**** Fixed ****/
    vi answer(q.size(), -1);
    int l, r, ans;
    sort(all(q));
    /**** Fixed ****/

    /**** Operations ****/
    auto add = [&](int id, int &res) {
        if(freq[c[id]] == 0)
            res++;
        freq[c[id]]++;
    };

    auto remove = [&](int id, int &res) {
        if(freq[c[id]] == 1)
            res--;
        freq[c[id]]--;
    };
    /**** Operations ****/
    
    /**** Fixed ****/
    r = -1;
    l = ans = 0;
    for(int i = 0; i < q.size(); i++) {
        while(l < q[i].l) remove(l++, ans);
        while(l > q[i].l) add(--l, ans);
        while(r < q[i].r) add(++r, ans);
        while(r > q[i].r) remove(r--, ans);
        answer[q[i].id] = ans;
    }
    /**** Fixed ****/

    /**** Printing Answer ****/    
    for(int i = 0 ; i < q.size() ; i++)
        cout << answer[i] << endl;
}

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

    c.resize(n);
    freq.assign(n + 1, 0);
    cin >> c;

    int l, r;
    vector<query> qe(q);
    for(int i = 0 ; i < q ; i++) {
        cin >> l >> r;
        qe[i] = query(l - 1, r - 1, i);
    }
    mo(qe);
}

void fast_io()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

#ifdef DHRUV_GHEEWALA
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    freopen("debug.txt", "w", stderr);
#endif
}

Measured memory_bytes: 31080