#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define SPEED ios_base::sync_with_stdio(false); cin.tie(NULL);
#define FOR(i, a, b) for (ll i = a; i < b; ++i)
#define RFOR(i, b, a) for (ll i = b; i >= a; --i)
#define ALL(x) x.begin(), x.end()
#define DEBUG(args...) { string _s = #args; replace(ALL(_s), ' ', '\0');\
replace(ALL(_s), ',', ' ');\
stringstream _ss(_s); istream_iterator<string> _it(_ss); _debug(_it, args);}
#define endl "\n"
#define F first
#define S second
#define pb(x) push_back(x)a
#define mp(x, y) make_pair(x, y)

using namespace std;
using namespace __gnu_pbds;

template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

void _debug(istream_iterator<string>) {}
template<typename T, typename... Args>
void _debug(istream_iterator<string> it, T first, Args... args) {
    cerr << ">> " << *it << " : " << first << endl; _debug(++it, args...);
}
template <typename T1, typename T2>
inline ostream& operator << (ostream& out, const pair<T1, T2>& p) {
    return out << "(" << p.F << ", " << p.S << ")";
}
template<typename T>
inline ostream& operator << (ostream& out, const vector<T>& v) {
    if (v.empty()) return out << "[]";
    else { out << '['; for (auto& e : v) { out << e << ", "; } return out << "\b\b]"; }
}
template<typename T>
inline ostream& operator << (ostream& out, const set<T>& s) {
    if (s.empty()) return out << "{}";
    else { out << '{'; for (auto& e : s) { out << e << ", "; } return out << "\b\b}"; }
}
template<typename T>
inline ostream& operator << (ostream& out, const unordered_set<T>& s) {
    return out << set<T>(ALL(s));
}
template<typename T1, typename T2>
inline ostream& operator << (ostream& out, const map<T1, T2>& m) {
    if (m.empty()) return out << "{}";
    out << '{'; for (auto& p : m) { out << p << ", "; } return out << "\b\b}";
}
template<typename T1, typename T2>
inline ostream& operator << (ostream& out, const unordered_map<T1, T2>& m) {
    return out << map<T1, T2>(ALL(m));
}
template<typename T>
inline ostream& operator << (ostream& out, const ordered_set<T>& s) {
    return out << set<T>(ALL(s));
}

typedef long long ll;
typedef long double ld;
typedef vector<long long> vll;
typedef pair<ll, ll> pll;
typedef vector<pair<ll, ll>> vpll;
typedef unordered_map<ll, ll> STll;

/**********************************************************************************
* SEGMENT TREE WITH DEBUGGER (WITH SAMPLE OPERATION)   @author: manishjoshi394
**********************************************************************************/
class SegmentTree {
    vector<ll> _tree;
    int n;

    int left(int v) const {
        return 2 * v;
    }
    int right(int v) const {
        return 2 * v + 1;
    }
    template<typename T>
    void build(int v, int l, int r, const vector<T>& arr) {
        if (l == r) {
            _tree[v] = arr[l];
        } else {
            int mid = l + (r - l) / 2;
            build(left(v), l, mid, arr);
            build(right(v), mid + 1, r, arr);

            _tree[v] = _tree[left(v)] + _tree[right(v)];
        }
    }
    void update(int v, int l, int r, int pos, ll new_val) {
        if (l == r) {
            _tree[v] = new_val;
        } else {
            int mid = l + (r - l) / 2;

            if (pos <= mid)
                update(left(v), l, mid, pos, new_val);
            else
                update(right(v), mid + 1, r, pos, new_val);

            _tree[v] = _tree[left(v)] + _tree[right(v)];
        }
    }
    ll query(int v, int l, int r, int ql, int qr) const {
        if (ql > qr)
            return 0;
        if (l == ql && r == qr) return _tree[v];
        int mid = l + (r - l) / 2;
        return query(left(v), l, mid, ql, min(mid, qr)) +
                   query(right(v), mid + 1, r, max(mid + 1, ql), qr);
    }
public:
    template<typename T>
    SegmentTree(const vector<T>& arr) {
        n = arr.size();
        _tree.resize(4 * n);
        build(1, 0, n - 1, arr);
    }
    SegmentTree(int _n, ll _init = 0) : SegmentTree(vector<ll>(_n, _init)) {}

    ll rmaxq(int l, int r) const {
        return query(1, 0, n - 1, l, r);
    }

    void update(int pos, ll new_val) {
        update(1, 0, n - 1, pos, new_val);
    }

    int size() const {
        return n;
    }
};
inline ostream& operator << (ostream& out, SegmentTree& SegTree) {
    vector<ll> vals;
    for (int i = 0; i < SegTree.size(); ++i) {
        vals.push_back(SegTree.rmaxq(i, i));
    }
    return out << vals;
}

/************************************** MAIN PROGRAM ********************************************/

int main()
{
   // freopen("input.txt", "r", stdin);
    SPEED
    int n, q;
    cin >> n >> q;
    vector<int> c(n);
    for (auto &e : c) cin >> e;
    vector<pair<int, int>> queries(q);
    for (auto &[l, r] : queries) {
        cin >> l >> r;
        l--, r--;
    }
    vector<vector<int>> posof(n + 1);
    for (int i = 0; i < n; ++i) {
        posof[c[i]].push_back(i);
    }
    vector<int> seq; for (int i = 0; i < q; ++i) seq.push_back(i);
    sort(ALL(seq), [&](auto x, auto y) {
        return queries[x].second > queries[y].second;
    });
    SegmentTree st(n + 1);
    for (int i = 0; i <= n; ++i) {
        if (!posof[i].empty()) {
            st.update(posof[i].back(), 1);
        }
    }

    int ptr = n - 1; // [ptr + 1 .. n - 1] has been erased
    vector<int> ans(q);
    for (auto idx : seq) {
        auto [l, r] = queries[idx];
        while (ptr > r) {
            int guy = c[ptr];
            assert(posof[guy].back() == ptr);
            st.update(posof[guy].back(), 0);
            posof[guy].pop_back();
            if (!posof[guy].empty()) st.update(posof[guy].back(), 1);

            ptr--;
        }
       // DEBUG(l, r, st)
        ans[idx] = st.rmaxq(l, n);
    }
    for (int i = 0; i < q; ++i) {
        cout << ans[i] << endl;
    }
}
/************************************** END OF PROGRAM ******************************************/
/** Stuff you should look for:
 * int overflow, array bounds, over-counting
 * special cases (n=1?), set/unordered_set TLE, multi-set/set error
 * do something instead of nothing and stay organized
 */


Measured memory_bytes: 57892