// compile: make data
// run: ./data < big.in > big.out && diff big.out big.ans
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#ifdef LOCAL
#include <debug/codeforces.h>
#define debug(x...) _debug_print(#x, x);
#define Debug(x...) _debug_print_format(#x, x);
#else
#define debug(x...)
#define Debug(x...)
#endif
template<typename...Args> void print_(Args...args){((cout<<args<<" "),...)<<endl;}
#define VI vector<int>
#define VII vector<vector<int>>
#define VIII vector<vector<vector<int>>>
#define rep(i,a,b) for(int i=(a);i<(int)(b);++i)
#define sz(v) ((int)(v).size())
#define print(...) print_(__VA_ARGS__);
#define FIND(a, x) ((find(a.begin(),a.end(),(x))!=a.end())?1:0)
#define cmin(x,...) x=min({(x), __VA_ARGS__})
#define cmax(x,...) x=max({(x), __VA_ARGS__})
#define INTMAX (int)(9223372036854775807)
#define INF (int)(1152921504606846976)
#define NaN (int)(0x8b88e1d0595d51d1)
#define double long double
#define int long long
#define MAXN 200010

struct mos {
    int S = 0;
    struct interval {
        int l, r, id;
    };
    vector<interval> q;
    void add_query(int l, int r) {
        q.push_back({l, r, sz(q)});
    }
    auto run(auto brute, auto inc, auto dec, auto get) {
        S = (int)sqrt(sz(q));
        sort(q.begin(), q.end(), [&](const interval &a, const interval &b) {
            if (a.l/S != b.l/S) return a.l < b.l;
            if ((a.l/S) & 1) return a.r < b.r;
            return a.r > b.r;
        });
        vector<int> res(sz(q));
        int cl = 0, cr = 0;
        rep(_, 0, sz(q)) {
            int l = q[_].l, r = q[_].r, id = q[_].id;
            if (!(_ % S)) {
                brute(cl = l, cr = r);
            }
            else {
                while (cl < l) dec(cl++);
                while (cl > l) inc(--cl);
                while (cr < r) inc(++cr);
                while (cr > r) dec(cr--);
            }
            res[id] = get();
        }
        return res;
    }
};

int corcomp(vector<int> &a) {
    int maxv = 0;
    vector<pair<int, int>> l(sz(a)), r(sz(a));
    rep(i, 0, sz(a)) l[i] = {a[i], i};
    sort(l.begin(), l.end());
    r[0] = {l[0].second, 0};
    rep(i, 1, sz(a)) {
        r[i].first = l[i].second;
        r[i].second = r[i-1].second + (l[i].first != l[i-1].first);
    }
    maxv = r.back().second;
    sort(r.begin(), r.end());
    rep(i, 0, sz(a)) a[i] = r[i].second;
    return maxv;
}


int32_t main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);

    int n, q; cin >> n >> q;
    vector<int> a(n);
    rep(i, 0, n) cin >> a[i];
    int N = corcomp(a);
    mos mo;
    while (q--) {
        int L, R; cin >> L >> R; --L, --R;
        mo.add_query(L, R);
    }
    int total = 0;
    vector<int> cnt(N+1);
    auto brute = [&](int l, int r) {
        fill(cnt.begin(), cnt.end(), 0);
        total = 0;
        rep(i, l, r+1) if (!(cnt[a[i]]++)) ++total;
    };
    auto inc = [&](int x) {
        if (!(cnt[a[x]]++)) ++total;
    };
    auto dec = [&](int x) {
        if (!(--cnt[a[x]])) --total;
    };
    auto get = [&]() {
        return total;
    };
    auto res = mo.run(brute, inc, dec, get);
    for (auto x: res) printf("%lld\n", x);

    return 0;
}