#define _USE_MATH_DEFIMES
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cctype>
#include <climits>
#include <clocale>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <regex>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

const int MOD = 1'000'000'007;
const int INF = 1'000'000'000; //1e9
const int NIL = -1;
const long long LINF = 1'000'000'000'000'000'000; // 1e18
const long double EPS = 1E-10;

template<class T, class S> inline bool chmax(T &a, const S &b){
    if(a < b){
        a = b; return true;
    }
    return false;
}
template<class T, class S> inline bool chmin(T &a, const S &b){
    if(b < a){
        a = b; return true;
    }
    return false;
}






template<class T> class SegmentTreeSum{
    int n = 0;
    std::vector<int> dat;
    T fill = 0;
public:
    SegmentTreeSum(){}
    SegmentTreeSum(int m, T fil = 0){
        fill = fil;
        int i = 1;
        while(i < m) i *= 2;
        n = i;
        dat.resize(2*i - 1);
        for(int j(0), j_len(2*i-1); j < j_len; ++j)
            dat[j] = fill;
    }

    void update(int k, T a){
        k += n - 1;
        int moto = dat[k];
        dat[k] = a;
        while(k){
            k = (k - 1) / 2;
            dat[k] += a - moto;
        }
    }

    void updateIncrease(int k, T a){
        update(k, dat[k+n-1] + a);
    }
    void updateIncrease(int k){
        updateIncrease(k, 1);
    }

    void updateDecrease(int k, T a){
        update(k, dat[k+n-1] - a);
    }
    void updateDecrease(int k){
        updateDecrease(k, 1);
    }

    T getSum(int a, int b, int k=0, int l=0, int r=-1){
        //[a, b[であることに注意
        if(r < 0) r = n;
        if(r <= a || b <= l) return fill;
        if(a <= l && r <= b) return dat[k];

        T vl = getSum(a, b, 2*k+1, l, (l+r)/2);
        T vr = getSum(a, b, 2*k+2, (l+r)/2, r);
        return vl + vr;
    }

    T getvalue(int k){
        return dat[k+n-1];
    }

    bool getExist(int l, int r){//全て非負と仮定
        //[l, r]
        return (getSum(l, r+1) > fill);
    }
};


int main(){
    int N, Q; std::cin >> N >> Q;
    std::vector<int> c(N), lst(N, NIL), ans(Q);
    //p[i] = {{R, L}, index}
    std::vector<std::pair<std::pair<int, int>, int>> p(Q);
    for(int i(0); i < N; ++i){
        std::cin >> c[i]; --c[i];
        }
    for(int i(0); i < Q; ++i){
        std::cin >> p[i].first.second >> p[i].first.first;
        --p[i].first.second; --p[i].first.first;
        p[i].second = i;
    }
    std::sort(std::begin(p), std::end(p));
    SegmentTreeSum<int> cnt(Q, 0);
    int R(-1);
    for(int i(0); i < Q; ++i){
        while(p[i].first.first > R){
            ++R;
            if(lst[c[R]] != NIL) cnt.updateDecrease(lst[c[R]]);
            cnt.updateIncrease(R);
            lst[c[R]] = R;
        }
        ans[p[i].second] = cnt.getSum(p[i].first.second, p[i].first.first + 1);
    }

    for(int i(0); i < Q; ++i){
        std::cout << ans[i] << "\n";
    }
    return 0;
}


Measured memory_bytes: 19484