#pragma GCC optimize ("-Ofast")
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define sz(a) (long long)a.size()
#define all(a) a.begin(), a.end()
#define reset(a, n) a.clear(), a.resize(n)
#ifndef ONLINE_JUDGE
#define cin ___in
#endif
std::ifstream ___in("input.in");
using namespace std;
using ll = long long;
typedef pair<ll, ll> pi;
typedef vector<ll> vec;
typedef vector<vector<ll> > vvec;
typedef vector<pair<ll, ll> > vecpi;
typedef vector<vector<pair<ll, ll> > > vvecpi;
typedef set<ll> seti;
typedef set<pair<ll, ll> > setpi;
typedef multiset<ll> mseti;
typedef multiset<pair<ll, ll> > msetpi;
typedef map<ll, ll> mpi;

static const bool tc = 0;
static const ll mod = LLONG_MAX - 24;

template <class T>
class segmentTree {
private:
        int _n, _cfg;
        const T ST_MAX_VAL;
        bool _stl;
        vector<T> _v[5];
        vector<typename vector<T>::iterator> _to;
        typename vector<T>::iterator _vstart;
        T *_start;
        void _lazySumUpdate(const int _node, const int _nowL, const int _nowR, const T _val) {
                bool _pending = (_val == 0);
                if(_cfg & 1) _v[0][_node] += (_pending ? _v[3][_node] : _val);
                if(_cfg & 2) _v[1][_node] += (_pending ? _v[3][_node] : _val);
                if(_cfg & 4) _v[2][_node] += (_nowR - _nowL + 1) * (_pending ? _v[3][_node] : _val);
                if(_nowL != _nowR) {
                        _v[3][2 * _node] += (_pending ? _v[3][_node] : _val);
                        _v[3][2 * _node + 1] += (_pending ? _v[3][_node] : _val);
                }
                _v[3][_node] = 0;
        }
        void _updateLazySums(const int _node, const int _nowL, const int _nowR, const int _tL, const int _tR) {
                if(_v[3][_node] != 0) _lazySumUpdate(_node, _nowL, _nowR, 0);
                if(_nowL > _tR || _nowR < _tL || _nowL == _nowR || (_tL <= _nowL && _nowR <= _tR)) return;
                int _m = (_nowL + _nowR) / 2;
                _updateLazySums(2 * _node, _nowL, _m, _tL, _tR);
                _updateLazySums(2 * _node + 1, _m + 1, _nowR, _tL, _tR);
                if(_cfg & 1) _v[0][_node] = min(_v[0][2 * _node], _v[0][2 * _node + 1]);
                if(_cfg & 2) _v[1][_node] = max(_v[1][2 * _node], _v[1][2 * _node + 1]);
                if(_cfg & 4) _v[2][_node] = _v[2][2 * _node] + _v[2][2 * _node + 1];
        }
        void _lazyAssignUpdate(const int _node, const int _nowL, const int _nowR, const T _val) {
                bool _pending = (_val == ST_MAX_VAL);
                if(_cfg & 1) _v[0][_node] = (_pending ? _v[4][_node] : _val);
                if(_cfg & 2) _v[1][_node] = (_pending ? _v[4][_node] : _val);
                if(_cfg & 4) _v[2][_node] = (_nowR - _nowL + 1) * (_pending ? _v[4][_node] : _val);
                if(_nowL != _nowR) {
                        _v[4][2 * _node] = (_pending ? _v[4][_node] : _val);
                        _v[4][2 * _node + 1] = (_pending ? _v[4][_node] : _val);
                }
                _v[4][_node] = ST_MAX_VAL;
        }
        void _updateLazyAssigns(const int _node, const int _nowL, const int _nowR, const int _tL, const int _tR) {
                if(_v[4][_node] != ST_MAX_VAL) _lazyAssignUpdate(_node, _nowL, _nowR, ST_MAX_VAL);
                if(_nowL > _tR || _nowR < _tL || _nowL == _nowR || (_tL <= _nowL && _nowR <= _tR)) return;
                int _m = (_nowL + _nowR) / 2;
                _updateLazyAssigns(2 * _node, _nowL, _m, _tL, _tR);
                _updateLazyAssigns(2 * _node + 1, _m + 1, _nowR, _tL, _tR);
                if(_cfg & 1) _v[0][_node] = min(_v[0][2 * _node], _v[0][2 * _node + 1]);
                if(_cfg & 2) _v[1][_node] = max(_v[1][2 * _node], _v[1][2 * _node + 1]);
                if(_cfg & 4) _v[2][_node] = _v[2][2 * _node] + _v[2][2 * _node + 1];
        }
        void _setUp(const int _node, const int _l, const int _r) {
                if(_l == _r) {
                        for(int i = 0; i < 3; ++i)
                                if((_cfg >> i) & 1) {
                                        _to[_l] = (_v[i].begin() + _node);
                                        break;
                                }
                        for(int i = 0; i < 3; ++i)
                                if((_cfg >> i) & 1) {
                                        if(_stl) _v[i][_node] = *(_vstart + _l - 1);
                                        else _v[i][_node] = *(_start + _l - 1);
                                }
                        return;
                }
                int _m = (_l + _r) / 2;
                _setUp(2 * _node, _l, _m);
                _setUp(2 * _node + 1, _m + 1, _r);
                if(_cfg & 1) _v[0][_node] = min(_v[0][2 * _node], _v[0][2 * _node + 1]);
                if(_cfg & 2) _v[1][_node] = max(_v[1][2 * _node], _v[1][2 * _node + 1]);
                if(_cfg & 4) _v[2][_node] = _v[2][2 * _node] + _v[2][2 * _node + 1];
        }
        void _addToInterval(const int _node, const int _nowL, const int _nowR, const int _tL, const int _tR, const T _val) {
                if(_v[3][_node] != 0) _lazySumUpdate(_node, _nowL, _nowR, 0);
                if(_nowL > _tR || _nowR < _tL) return;
                if(_tL <= _nowL && _nowR <= _tR) {
                        _lazySumUpdate(_node, _nowL, _nowR, _val);
                        return;
                }
                int _m = (_nowL + _nowR) / 2;
                _addToInterval(2 * _node, _nowL, _m, _tL, _tR, _val);
                _addToInterval(2 * _node + 1, _m + 1, _nowR, _tL, _tR, _val);
                if(_cfg & 1) _v[0][_node] = min(_v[0][2 * _node], _v[0][2 * _node + 1]);
                if(_cfg & 2) _v[1][_node] = max(_v[1][2 * _node], _v[1][2 * _node + 1]);
                if(_cfg & 4) _v[2][_node] = _v[2][2 * _node] + _v[2][2 * _node + 1];
        }
        void _assignToInterval(const int _node, const int _nowL, const int _nowR, const int _tL, const int _tR, const T _val) {
                if(_v[4][_node] != ST_MAX_VAL) _lazyAssignUpdate(_node, _nowL, _nowR, ST_MAX_VAL);
                if(_nowL > _tR || _nowR < _tL) return;
                if(_tL <= _nowL && _nowR <= _tR) {
                        _lazyAssignUpdate(_node, _nowL, _nowR, _val);
                        return;
                }
                int _m = (_nowL + _nowR) / 2;
                _assignToInterval(2 * _node, _nowL, _m, _tL, _tR, _val);
                _assignToInterval(2 * _node + 1, _m + 1, _nowR, _tL, _tR, _val);
                if(_cfg & 1) _v[0][_node] = min(_v[0][2 * _node], _v[0][2 * _node + 1]);
                if(_cfg & 2) _v[1][_node] = max(_v[1][2 * _node], _v[1][2 * _node + 1]);
                if(_cfg & 4) _v[2][_node] = _v[2][2 * _node] + _v[2][2 * _node + 1];
        }
        T _intervalSum(const int _node, const int _nowL, const int _nowR, const int _tL, const int _tR) {
                if(_tL <= _nowL && _nowR <= _tR) return _v[2][_node];
                int _m = (_nowL + _nowR) / 2;
                T _s = 0;
                if(_tL <= _m) _s += _intervalSum(2 * _node, _nowL, _m, _tL, _tR);
                if(_tR > _m) _s += _intervalSum(2 * _node + 1, _m + 1, _nowR, _tL, _tR);
                return _s;
        }
        T _minRange(const int _node, const int _nowL, const int _nowR, const int _tL, const int _tR) {
                if(_tL <= _nowL && _nowR <= _tR) return _v[0][_node];
                int _m = (_nowL + _nowR) / 2;
                T _min = ST_MAX_VAL;
                if(_tL <= _m) _min = min(_min, _minRange(2 * _node, _nowL, _m, _tL, _tR));
                if(_tR > _m) _min = min(_min, _minRange(2 * _node + 1, _m + 1, _nowR, _tL, _tR));
                return _min;
        }
        T _maxRange(const int _node, const int _nowL, const int _nowR, const int _tL, const int _tR) {
                if(_tL <= _nowL && _nowR <= _tR) return _v[1][_node];
                int _m = (_nowL + _nowR) / 2;
                T _max = -ST_MAX_VAL < 0ll ? -ST_MAX_VAL : 0;
                if(_tL <= _m) _max = max(_max, _maxRange(2 * _node, _nowL, _m, _tL, _tR));
                if(_tR > _m) _max = max(_max, _maxRange(2 * _node + 1, _m + 1, _nowR, _tL, _tR));
                return _max;
        }
        void _resize(const int _new) {
                _n = _new;
                for(int i = 0; i < 5; ++i)
                        if(_cfg & (1 << i)) _v[i].resize(4 * _new + 1);
                        else _v[i].clear();
                _to.clear();
                _to.resize(_new + 1);
        }
        void _setPos(const int _node, const int _l, const int _r, const int _p, const int _val) {
                if(_l == _r) {
                        for(int i = 0; i < 3; ++i)
                                if((_cfg >> i) & 1) _v[i][_node] = _val;
                        return;
                }
                int _m = (_l + _r) / 2;
                if(_p <= _m) _setPos(2 * _node, _l, _m, _p, _val);
                else _setPos(2 * _node + 1, _m + 1, _r, _p, _val);
                if(_cfg & 1) _v[0][_node] = min(_v[0][2 * _node], _v[0][2 * _node + 1]);
                if(_cfg & 2) _v[1][_node] = max(_v[1][2 * _node], _v[1][2 * _node + 1]);
                if(_cfg & 4) _v[2][_node] = _v[2][2 * _node] + _v[2][2 * _node + 1];
        }
        void _addOnPos(const int _node, const int _l, const int _r, const int _p, const int _val) {
                if(_l == _r) {
                        for(int i = 0; i < 3; ++i)
                                if((_cfg >> i) & 1) _v[i][_node] += _val;
                        return;
                }
                int _m = (_l + _r) / 2;
                if(_p <= _m) _addOnPos(2 * _node, _l, _m, _p, _val);
                else _addOnPos(2 * _node + 1, _m + 1, _r, _p, _val);
                if(_cfg & 1) _v[0][_node] = min(_v[0][2 * _node], _v[0][2 * _node + 1]);
                if(_cfg & 2) _v[1][_node] = max(_v[1][2 * _node], _v[1][2 * _node + 1]);
                if(_cfg & 4) _v[2][_node] = _v[2][2 * _node] + _v[2][2 * _node + 1];
        }
        T _on(const int _p) {
                return *_to[_p];
        }
        void _upd(const int _node, const int _nowL, const int _nowR) {
                if((_cfg & 8) && _v[3][_node] != 0) _lazySumUpdate(_node, _nowL, _nowR, 0);
                if((_cfg & 16) && _v[4][_node] != ST_MAX_VAL) _lazyAssignUpdate(_node, _nowL, _nowR, ST_MAX_VAL);
                if(_nowL == _nowR) return;
                int _m = (_nowL + _nowR) / 2;
                _upd(2 * _node, _nowL, _m);
                _upd(2 * _node + 1, _m + 1, _nowR);
                if(_cfg & 1) _v[0][_node] = min(_v[0][2 * _node], _v[0][2 * _node + 1]);
                if(_cfg & 2) _v[1][_node] = max(_v[1][2 * _node], _v[1][2 * _node + 1]);
                if(_cfg & 4) _v[2][_node] = _v[2][2 * _node] + _v[2][2 * _node + 1];
        }
public:
        /// 16  8   4   2   1
        /// LPA LPS SUM MAX MIN
        segmentTree():
        _n(0), _cfg(0), ST_MAX_VAL(-1ll + (1ll << (sizeof(T) * 8 - (T)(((T)0 >= 0 && (T)~0 >= 0) ^ 1)))) {}
        void setUp(T *_a, T *_b, const int _newcfg) {
                _cfg = _newcfg; _resize(_b - _a + 1); _start = _a; _stl = 0;
                fill(_v[0].begin(), _v[0].end(), ST_MAX_VAL);
                fill(_v[4].begin(), _v[4].end(), ST_MAX_VAL);
                for(int i = 1; i < 4; ++i) fill(_v[i].begin(), _v[i].end(), 0);
                _setUp(1, 1, _n);
        }
        void setUp(typename vector<T>::iterator _a, typename vector<T>::iterator _b, const int _newcfg) {
                _cfg = _newcfg; _resize(_b - _a + 1); _vstart = _a; _stl = 1;
                fill(_v[0].begin(), _v[0].end(), ST_MAX_VAL);
                fill(_v[4].begin(), _v[4].end(), ST_MAX_VAL);
                for(int i = 1; i < 4; ++i) fill(_v[i].begin(), _v[i].end(), 0);
                _setUp(1, 1, _n);
        }
        void setUp(const int _sz, const int _newcfg) {
                _cfg = _newcfg; _resize(_sz);
                fill(_v[0].begin(), _v[0].end(), ST_MAX_VAL);
                fill(_v[4].begin(), _v[4].end(), ST_MAX_VAL);
                for(int i = 1; i < 4; ++i) fill(_v[i].begin(), _v[i].end(), 0);
        }
        void addToInterval(const int _l, const int _r, const int _val) {
                if((_cfg & 8) == 0) exit(-1);
                if(_cfg & 16) _updateLazyAssigns(1, 1, _n, _l, _r);
                _addToInterval(1, 1, _n, _l, _r, _val);
        }
        void assignToInterval(const int _l, const int _r, const int _val) {
                if((_cfg & 16) == 0) exit(-1);
                if(_cfg & 8) _updateLazySums(1, 1, _n, _l, _r);
                if(_cfg & 16) _updateLazyAssigns(1, 1, _n, _l, _r);
                _assignToInterval(1, 1, _n, _l, _r, _val);
        }
        void addOnPos(const int _p, const int _val) {
                if(_cfg & 8)_updateLazySums(1, 1, _n, _p, _p);
                if(_cfg & 16) _updateLazyAssigns(1, 1, _n, _p, _p);
                _addOnPos(1, 1, _n, _p, _val);
        }
        void setPos(const int _p, const int _val) {
                if(_cfg & 8)_updateLazySums(1, 1, _n, _p, _p);
                if(_cfg & 16) _updateLazyAssigns(1, 1, _n, _p, _p);
                _setPos(1, 1, _n, _p, _val);
        }
        T intervalSum(const int _l, const int _r) {
                if((_cfg & 4) == 0) exit(-1);
                if(_cfg & 8) _updateLazySums(1, 1, _n, _l, _r);
                if(_cfg & 16) _updateLazyAssigns(1, 1, _n, _l, _r);
                return _intervalSum(1, 1, _n, _l, _r);
        }
        T minRange(const int _l, const int _r) {
                if((_cfg & 1) == 0) exit(-1);
                if(_cfg & 8) _updateLazySums(1, 1, _n, _l, _r);
                if(_cfg & 16) _updateLazyAssigns(1, 1, _n, _l, _r);
                return _minRange(1, 1, _n, _l, _r);
        }
        T maxRange(const int _l, const int _r) {
                if((_cfg & 2) == 0) exit(-1);
                if(_cfg & 8) _updateLazySums(1, 1, _n, _l, _r);
                if(_cfg & 16) _updateLazyAssigns(1, 1, _n, _l, _r);
                return _maxRange(1, 1, _n, _l, _r);
        }
        void print() {
                if(_cfg & 8) _updateLazySums(1, 1, _n, 1, _n);
                if(_cfg & 16) _updateLazyAssigns(1, 1, _n, 1, _n);
                _upd(1, 1, _n);
                for(int i = 1; i <= _n; ++i) cout << _on(i) << " ";
                cout << "\n";
        }
        vector<T> toVector() {
                if(_cfg & 8) _updateLazySums(1, 1, _n, 1, _n);
                if(_cfg & 16) _updateLazyAssigns(1, 1, _n, 1, _n);
                _upd(1, 1, _n);
                vector<T> _vv(_n + 1);
                for(int i = 1; i <= _n; ++i) _vv[i] = _on(i);
        }
        T quickSelect(const int _kth) {
                if((_cfg & 4) == 0 || _kth > intervalSum(1, _n)) exit(-1);
                T _l = 0, _r = _n + 1;
                while(_l < _r) {
                        T _m = (_l + _r) >> 1;
                        if(_kth <= intervalSum(1, _m)) _r = _m;
                        else _l = _m + 1;
                }
                return _l;
        }
};

void solve() {
        ll n, q;
        cin >> n >> q;
        vec a(n + 1), L(n + 1);
        vecpi b(q + 1), bb;
        map<pi, ll> mp;
        for(int i = 1; i <= n; ++i) cin >> a[i];
        for(int i = 1; i <= q; ++i) cin >> b[i].fi >> b[i].se;
        bb = b;
        segmentTree<ll> seg;
        seg.setUp(n + 1, 4);
        sort(1 + all(b), [] (pi a, pi b) {
                        if(a.se != b.se) return a.se < b.se;
                        else return a.fi < b.fi;
        });
        reverse(1 + all(b));
        ll last = 0;
        while(b.size() > 1) {
                ll l = b.back().fi;
                ll r = b.back().se;
                b.pop_back();
                while(last < r) {
                        ++last;
                        if(L[a[last]] != 0) seg.addOnPos(L[a[last]], -1);
                        seg.addOnPos(last, 1);
                        L[a[last]] = last;
                }
                mp[{l, r}] = seg.intervalSum(l, r);
        }
        for(int i = 1; i <= q; ++i) cout << mp[bb[i]] << "\n";
}

int main() {
        srand(time(0));
        int T = 1;
        if(tc) cin >> T;
        for(int i = 1; i <= T; ++i) {
                #ifndef ONLINE_JUDGE
                cout << "----- " << i << " -----\n";
                #endif
                solve();
        }
        return 0;
}


Measured memory_bytes: 78064