#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define REP(i, start, end) for (ll i = start, i##Len = (end); i < i##Len; ++i)
#define REPR(i, start, end) for (ll i = start, i##Len = (end); i > i##Len; --i)
using ll = long long;
using namespace std;

template <class T>
class SegmentTree
{
private:
    int _size = 1;
    T _def;
    std::vector<T> _nodes;
    std::function<T(T, T)> _op;
    std::function<T(T, T)> _update_op;

public:
    SegmentTree(int size, T default_value, std::function<T(T, T)> op,
                std::function<T(T, T)> update_op)
        : _def(default_value), _op(op), _update_op(update_op)
    {
        while (_size < size)
            _size *= 2;
        _nodes = std::vector<T>(2 * _size, default_value);
    }

    SegmentTree(std::vector<T> nodes, T default_value, std::function<T(T, T)> op,
                std::function<T(T, T)> update_op)
        : _def(default_value), _op(op), _update_op(update_op)
    {
        int real_size = nodes.size();
        while (_size < real_size)
            _size *= 2;
        _nodes = std::vector<T>(2 * _size, default_value);
        for (int i = 0; i < real_size; ++i)
            _nodes[i + _size] = nodes[i];
        for (int i = _size - 1; i >= 0; --i)
            _nodes[i] = _op(_nodes[i * 2], _nodes[i * 2 + 1]);
    }

    T find(int l, int r)
    {
        return find(l, r, 1, 0, _size);
    }

    T find(int l, int r, int index, int cover_l, int cover_r)
    {
        if (cover_r <= l || r <= cover_l)
            return _def;
        if (l <= cover_l && cover_r <= r)
            return _nodes[index];
        return _op(find(l, r, index * 2, cover_l, (cover_l + cover_r) >> 1),
                   find(l, r, index * 2 + 1, (cover_l + cover_r) >> 1, cover_r));
    }

    void update(int index, T value)
    {
        index += _size;
        _nodes[index] = _update_op(_nodes[index], value);
        while (index > 0)
        {
            index >>= 1;
            _nodes[index] = _op(_nodes[index * 2], _nodes[index * 2 + 1]);
        }
    }
};

int main()
{
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);

    ll N, Q;
    cin >> N >> Q;
    vector<ll> a(N), dup(N + 1, -1), prev_i(N + 1, -1);
    REP(i, 0, N)
    {
        cin >> a[i];
        if (dup[a[i]] != -1)
        {
            prev_i[i] = dup[a[i]];
        }
        dup[a[i]] = i;
    }

    vector<pair<int, int>> query(Q);
    REP(i, 0, Q)
    {
        cin >> query[i].first >> query[i].second;
    }
    vector<int> order(Q), ans(Q);
    iota(order.begin(), order.end(), 0);
    sort(order.begin(), order.end(), [&](int i, int j) { return query[i].second < query[j].second; });

    auto segt = SegmentTree<int>(
        N + 10, 0, [](int x, int y) { return x + y; }, [](int x, int y) { return x + y; });
    int j = 0;

    REP(i, 0, N + 1)
    {
        while (j < Q && query[order[j]].second == i)
        {
            ans[order[j]] = segt.find(query[order[j]].first - 1, query[order[j]].second);
            ++j;
        }
        segt.update(i, 1);
        if (prev_i[i] != -1)
            segt.update(prev_i[i], -1);
    }

    for (auto &x : ans)
        cout << x << "\n";
}


Measured memory_bytes: 27444