#include <bits/stdc++.h>

#define debug(x) cout <<"DEBUG"<<" "<< #x << ":" << x << '\n'
#define rep(i,n) for(int_fast32_t i = 0; i < ((int_fast32_t)(n)); i++)   // 0-indexed up
#define rep1(i,n) for(int_fast32_t i = 1; i <= ((int_fast32_t)(n)); i++) // 1-indexed up
#define rrep(i,n) for(int_fast32_t i = ((int_fast32_t)(n)-1); i >= 0; i--)  // 0-indexed down
#define rrep1(i,n) for(int_fast32_t i = ((int_fast32_t)(n)); i >= 1; i--)   // 1-indexed down
#define all(x) (x).begin(),(x).end()

using namespace std;

template<typename T>
using vec = vector<T>;
using i32 = int_fast32_t;
using i64 = int_fast64_t;
using u32 = uint_fast32_t;
using u64 = uint_fast64_t;
using ll = long long;
using ld = long double;
using vi = vec<int_fast32_t>;
using vl = vec<int_fast64_t>;
using vld = vec<ld>;
using vii = vec<vi>;
using PII = pair<int_fast32_t, int_fast32_t>;

template<class T>
using maxheap = std::priority_queue<T>;
template<class T>
using minheap = std::priority_queue<T, std::vector<T>, std::greater<T>>;

template<class T,class U> inline bool chmax(T &a, const U &b){if(a<b){a=b;return 1;}return 0;}
template<class T,class U> inline bool chmin(T &a, const U &b){if(a>b){a=b;return 1;}return 0;}

const ld Pi = std::acos(-1.0L);
constexpr ll infll = (1LL<<62)-1;
constexpr int inf = (1<<30)-1;
const int mod = 1000000007;
// const int mod = 998244353;


std::set<i32> st;


/*FUNCs=================================================*/
// Mo's algorithm
// 区間クエリの並べ替え順の保持と区間の伸縮による遷移、実行結果の格納を担う。区間は半開区間[l,r)
struct mo_s_algorithm {
    using i32 = int_fast32_t;
    i32 sqrt_n;
    i32 idx_l, idx_r;
    std::vector<i32> query_order;
    std::vector<std::pair<i32, i32>> &query_ranges;

    explicit mo_s_algorithm(std::vector<std::pair<i32, i32>> &query_ranges):
            query_ranges(query_ranges), query_order(query_ranges.size()), sqrt_n((i32)std::sqrt(query_ranges.size())), idx_l(0), idx_r(0)
    {
        for(i32 i = 0; i < query_ranges.size(); ++i) query_order[i] = i;
        std::sort(query_order.begin(), query_order.end(), [&](i32 a, i32 b) {
            if(query_ranges[a].first / sqrt_n != query_ranges[b].first / sqrt_n) return query_ranges[a].first < query_ranges[b].first;
            else if((query_ranges[a].first / sqrt_n)&1) return query_ranges[a].second < query_ranges[b].second;
            else return query_ranges[a].second > query_ranges[b].second;
        });
    }

    template<class T = i32>
    void execute(vector<T> &answer_container, T initial_ans) {
        T current_answer = initial_ans;
        if(answer_container.size() != query_ranges.size()) printf("error! size is not same!");
        for(auto &id : query_order) {
            while(idx_l > query_ranges[id].first) --idx_l, add(idx_l, current_answer);
            while(idx_r < query_ranges[id].second) add(idx_r, current_answer), ++idx_r;
            while(idx_l < query_ranges[id].first) del(idx_l, current_answer), ++idx_l;
            while(idx_r > query_ranges[id].second) --idx_r, del(idx_r, current_answer);
            answer_container[id] = current_answer;
        }
    }

    template<class T = i32>
    inline void add(i32 idx, T &target);

    template<class T = i32>
    inline void del(i32 idx, T &target);
};

i32 c[500100];
i32 c_mp[500100];  // 区間内の各cの数を記録する

template<class T>
void mo_s_algorithm::add(i32 idx, T &target) {
    ++c_mp[c[idx]];
    if(c_mp[c[idx]] == 1) {
        ++target;
    }
}

template<class T>
void mo_s_algorithm::del(i32 idx, T &target) {
    --c_mp[c[idx]];
    if(c_mp[c[idx]] == 0) {
        --target;
    }
}


/*MAIN==================================================*/
signed main(){
    double START_TIME = clock();
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
//    cout << fixed << setprecision(15);

    i32 n,q; cin >> n >> q;
    rep(i,n) cin >> c[i];
    vec<PII> queries(q);
    rep(i,q) {
        cin >> queries[i].first >> queries[i].second;
        --queries[i].first;
    }
    vi ans(q);


    mo_s_algorithm Mo(queries);
    Mo.execute<i32>(ans, 0);
    for(auto &a : ans) printf("%d\n", int(a));

//     printf("ElapsedTime: %5.3f ms\n",1000*((clock()-START_TIME)/CLOCKS_PER_SEC));
}


Measured memory_bytes: 27172