#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define int ll

template<typename T1,typename T2> inline void chmin(T1 &a, T2 b){ if(a > b) a = b; }
template<typename T1,typename T2> inline void chmax(T1 &a, T2 b){ if(a < b) a = b; }

#define REP(i,n) for(int i=0;i<n;++i)
#define SORT(name) sort(name.begin(), name.end())
#define ZERO(p) memset(p, 0, sizeof(p))
#define MINUS(p) memset(p, -1, sizeof(p))
#if 0
#  define DBG(fmt, ...) printf(fmt, ##__VA_ARGS__)
#else
#  define DBG(fmt, ...)
#endif

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const double DINF = std::numeric_limits<double>::infinity();
const int MOD = 1000000007;
const int MAX_N = 500010;

template<typename T>
class BITree {
    public:
        BITree(int n) : m_N(n + 1) { m_Tree.assign(m_N, 0); }
        // [1, i] の合計値を返す (log m_N)
        // 閉区間であることに注意
        T Sum(int i) {
            assert(i >= 0 && i < m_N);
            T s = 0;
            while(i > 0) { s += m_Tree[i]; i -= i & -i; }
            return s;
        }
        // [i, j] の合計値を返す (log m_N)
        // i < j
        // 閉区間であることに注意
        T Sum(int i, int j) {
            assert(i <= j);
            return Sum(j) - Sum(i-1);
        }
        // i 番目の要素(1-indexed)に x を足して更新 O(log m_N)
        void Add(int i, T x){ while(i < m_N) { m_Tree[i] += x; i += i & -i; } }
    private:
        int m_N;            // 要素数
        vector<T> m_Tree;   // BIT 本体
};

// 数列の範囲 [l, r] 内にある数字の種類数を返す
// O(N log N)くらい (N: 配列の要素数 && 数字の種類数)
// 事前にどんなクエリが与えられるかがすべてわかっている必要がある
// 引数
//   v: 数列 (数字の種類 1～N)
//   q: クエリ。数列の範囲 [l, r] の pair (1 <= l,r <= N)
// 返り値
//   map の key: 範囲 [l, r]
//   map の value: key の時の答え（種類数）
map< pair<int, int>, int> RangeSetQuery(const vector<int>& v, const vector< pair<int, int> >& q) {
    const int n = v.size();
    vector< vector<int> > point_st(n + 10, vector<int>());
    vector< vector<int> > point_lr(n + 10, vector<int>());

    for(auto& q_tmp : q) { point_lr[q_tmp.first].push_back(q_tmp.second); }

    // 同じ数字が出てくる区間に変換
    // -> [l, r] に存在する区間を全体から引くことで解が求まる
    vector<int> prev(n + 10, -1);    // 前回の i があった場所
    for(int i = 0; i < n; ++i) {
        if(prev[v[i]] >= 0) { point_st[prev[v[i]] + 1].push_back(i + 1); }
        prev[v[i]] = i;
    }

    // 同じ数字が出る区間を [s,t] としたとき、
    // l <= s && t <= r を満たすなら、その数字は重複して出現している。
    // -> 二次元平面にプロットしたとき x 大きい方から見ていって
    // r より小さい t の数が重複した数
    BITree<int> fenwick(n + 10);
    map< pair<int, int>, int> ret;
    for(int x = n; x >= 0; --x) {
        for(auto y : point_st[x]) {
            fenwick.Add(y + 1, 1);
        }
        for(auto y : point_lr[x]) {
            // これまで出ている (s, t) のうち y 以下のものの数
            ret[make_pair(x, y)] = (y - x + 1) - fenwick.Sum(1, y + 1);
        }
    }

    return ret;
}

int N, Q;
vector<int> C;
vector< pair<int, int> > LR;


signed main() {
    cin.tie(0); cout.tie(0);
    ios::sync_with_stdio(false);

    cin >> N >> Q;
    C.resize(N);
    REP(i, N) {
        cin >> C[i];
    }
    REP(i, Q) {
        int l, r;
        cin >> l >> r;
        LR.push_back(make_pair(l, r));
    }

    auto ans = RangeSetQuery(C, LR);

    for(auto lr : LR) {
        printf("%lld\n", ans[lr]);
    }

    return 0;
}


Measured memory_bytes: 102848