/*
**    Author : Dhiraj Govindvira
**      Date : 09-Sep-2020 ~ Wednesday
**      Time : 08:08:29 PM
*/

#ifdef Dhiraj
    #include "D:/dhiraj/Programming/debug.h"
#else
    #include <bits/stdc++.h>
    using namespace std;
    #define d(...) 11
    #define cerr if(0) cerr
#endif

// Macro --------------------------------------------------------------------

#define ll                  long long int
#define FOR(i, a, b, s)     for(ll i = (a); ((s) > 0 ? i < (b) : i > (b)); i += (s))
#define FOR1(b)             FOR(i, 0, b, 1)
#define FOR2(i, b)          FOR(i, 0, b, 1)
#define FOR3(i, a, b)       FOR(i, a, b, (a) <= (b) ? 1 :-1)
#define FOR4(i, a, b, s)    FOR(i, a, b, s)
#define GET5(a, b, c, d, e, ...) e
#define FORC(...)           GET5(__VA_ARGS__, FOR4, FOR3, FOR2, FOR1)
#define loop(...)           FORC(__VA_ARGS__)(__VA_ARGS__)
#define all(x)              x.begin(), x.end()
#define rall(x)             x.rbegin(), x.rend()
#define endl                '\n'

// Template -----------------------------------------------------------------

// multiple input
template <typename... T> 
inline void inp(T&... args) {
    ((cin >> args), ...);
}
// scan vector
template <typename T> 
inline istream& operator >>(istream &in, vector<T> &a) {
    for(auto &x : a) in >> x;
    return in;
}
// scan pair
template <typename T, typename U> 
inline istream& operator >>(istream &in, pair<T, U> &a) {
    in >> a.first >> a.second; 
    return in;
}

// Solve --------------------------------------------------------------------

/*
0 based index
Mo m;
m.add_query(l, r, id);
m.solve();
*/

const ll block_size = 777;
struct Query
{
    ll l, r, id;
    Query() {};
    Query(ll _l, ll _r, ll _id)
    {
        l = _l;
        r = _r;
        id = _id;
    }
    friend bool operator < (const Query &lhs, const Query &rhs) {
        ll x = lhs.l / block_size;
        ll y = rhs.l / block_size;
        return (x != y) ? (x < y) : ((x & 1) ? (lhs.r < rhs.r) : (lhs.r > rhs.r));
    }
    friend void deprint(Query &q)
    {
        cerr << "(" << q.l << "," << q.r << ") ";
        cerr << "id : " << q.id;
    }
};

ll n, mx = 5e5 + 5;
vector<ll> a, fre(mx);

struct Mo
{
    ll ans;
    vector<ll> sol;
    vector<Query> qry;

    void add_query(ll l, ll r, ll id)
    {
        qry.emplace_back(Query(l, r, id));
        sol.emplace_back(0);
    }

    void add(ll i)
    {
        d(i, a[i], fre[a[i]]);
        fre[a[i]]++;
        ans += (fre[a[i]] == 1);
    }
    void remove(ll i)
    {
        d(-i, a[i], fre[a[i]]);
        fre[a[i]]--;
        ans -= (fre[a[i]] == 0);
    }

    void solve()
    {
        ans = 0;
        sort(all(qry));

        ll l = 0, r = -1;
        for(auto &q : qry)
        {
            while(l > q.l) add(--l);
            while(r < q.r) add(++r);
            while(l < q.l) remove(l++);
            while(r > q.r) remove(r--);
            sol[q.id] = ans;
            d(q, ans);
        }
        
        for(auto &X : sol) {
            cout << X << "\n";
        }
    }
};

void solve(int &T)
{
    ll q;
    cin >> n >> q;
    
    a.resize(n);
    cin >> a;

    Mo m;
    loop(i, q) {
        ll l, r;
        cin >> l >> r;
        m.add_query(l - 1, r - 1, i);
    }
    m.solve();
}

// Main ---------------------------------------------------------------------

int main()
{
    #ifdef Dhiraj
        freopen("D:/dhiraj/Programming/i1.txt", "r", stdin);
        freopen("D:/dhiraj/Programming/o1.txt", "w", stdout);
        freopen("D:/dhiraj/Programming/e1.txt", "w", stderr);
    #endif

    ios::sync_with_stdio(false);
    cin.tie(0);

    int t = 1;
    for(int i = 1; i <= t; i++) {
        cerr << "Case #" << i << "\n";
        solve(i);
    }
    return 0;
}

Measured memory_bytes: 31368