#include <bits/stdc++.h>
#include <unistd.h>
#include <sys/time.h>
#include <stdlib.h>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> P;
typedef pair<P, ll> T;
typedef pair<long double , ll> Ps;
typedef pair<ll, bool> Pb;

const ll INF = 1e18;
const ll fact_table = 3200008;
long double Pi = 3.1415926535897932384626;

priority_queue <ll> pql;
priority_queue <P> pqp;
priority_queue <P> bag;
//big priority queue
priority_queue <ll, vector<ll>, greater<ll> > pqls;
priority_queue <P, vector<P>, greater<P> > pqps;
//small priority queue
//top pop

ll dx[8] = {1, 0, -1, 0, 1, 1, -1, -1};
ll dy[8] = {0, 1, 0, -1, 1, -1, -1, 1};
//↓,→,↑,←


#define endl "\n"
#ifdef ENJAPMA
#undef endl
#endif

#define p(x) cout<<x<<endl;
#define el cout<<endl;
#define pe(x) cout<<x<<" ";
#define ps(x) cout<<fixed<<setprecision(25)<<x<<endl;
#define pu(x) cout<<(x);
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define CLEAR(a) a = decltype(a)();
#define pc(x) cout << x << ",";
#define rep(i, n) for (ll i = 0; i < (n); i ++)

// const ll mod = 998244353ll;
const ll mod = 1000000007ll;

ll mypow(ll a, ll b, ll mod) {ll x = 1; while (b) {while (!(b & 1)) {(a *= a) %= mod; b >>= 1;}(x *= a) %= mod; b--;} return x;}
void YES(bool cond) { if (cond) { p("YES");} else { p("NO");} return;}
void Yes(bool cond) { if (cond) { p("Yes");} else { p("No");} return;}
void line() { p("--------------------"); return;}

/*
ll fact[fact_table + 5], rfact[fact_table + 5];

void c3_init() {
    fact[0] = rfact[0] = 1;
    for (ll i = 1; i <= fact_table; i++) {
        fact[i] = (fact[i - 1] * i) % mod;
    }
    rfact[fact_table] = mypow(fact[fact_table], mod - 2, mod);
    for (ll i = fact_table; i >= 1; i--) {
        rfact[i - 1] = rfact[i] * i;
        rfact[i - 1] %= mod;
    }
    return;
}
ll c3(ll n, ll r) {
    return (((fact[n] * rfact[r]) % mod ) * rfact[n - r]) % mod;
}
*/
struct Timer {
    int64_t start;
    const int64_t CYCLES_PER_SEC = 2800000000;
    Timer() { reset(); }
    void reset() { start = getCycle(); }
    inline double get() { return (double)(getCycle() - start) / CYCLES_PER_SEC; }
    inline int64_t getCycle() {
        uint32_t low, high;
        __asm__ volatile ("rdtsc" : "=a" (low), "=d" (high));
        return ((int64_t)low) | ((int64_t)high << 32);
    }
};

struct SegmentTree {
private:
    int n;
    vector<ll> node;
public:
    SegmentTree(vector<ll> v) {
        int sz = (int)v.size();
        n = 1; while(n < sz) n *= 2;
        node.resize(2*n-1, 0);
 
        for(int i=0; i<sz; i++) node[i+n-1] = v[i];
        for(int i=n-2; i>=0; i--) node[i] = node[i*2+1] + node[i*2+2];
    }
 
    void update(int k, ll val) {
        // update node[k] to val (0-indexed)
        k += (n - 1);
        node[k] = val;
        while(k > 0) {
            k = (k - 1) / 2;
            node[k] = node[2*k+1] + node[2*k+2];
        }
    }
 
    ll getsum(int a, int b, int k=0, int l=0, int r=-1) {
        //sum of [a, b)
        if(r < 0) r = n;
        if(b <= l || r <= a) return 0;
        if(a <= l && r <= b) return node[k];
 
        ll vl = getsum(a, b, 2*k+1, l, (l+r)/2);
        ll vr = getsum(a, b, 2*k+2, (l+r)/2, r);
        return vl + vr;
    }
};


bool multicase = false;

ll n, m, k, w, a, b, c, d, e, h, q, ans, sum, l;

typedef vector<ll> vec;
typedef vector<vector<ll>> mat;

ll lef[500005], before_left[500005];

struct query{
    ll l, r, id;
};

bool asc(const query& left, const query& right){
    return left.r < right.r;
}

void del(SegmentTree& seg, ll value){
    if (value < 0) return;
    ll now = seg.getsum(value, value + 1);
    seg.update(value, now - 1);
    return;
}

void add(SegmentTree& seg, ll value){
    if (value < 0) return;
    ll now = seg.getsum(value, value + 1);
    seg.update(value, now + 1);
    return;
}

void update(SegmentTree& seg, vec& x, ll idx){
    // del(seg, before_left[x[idx]]);
    add(seg, lef[x[idx]]);
    before_left[x[idx]] = lef[x[idx]];
    lef[x[idx]] = idx;
    return;
}



void solve() {
    cin >> n >> q;
    vec x(n);
    for(int i=0;i<n;i++){
        cin >> x[i];
    }
    SegmentTree seg(vec(n+10));
    vector<query> v;
    for(int i=0;i<q;i++){
        cin >> a >> b;
        a--; b--;
        v.push_back({a, b, i});
    }
    for(int i=1;i<=n;i++){
        lef[i] = before_left[i] = -1;
    }
    sort(v.begin(), v.end(), asc);
    int before_r = 0;
    vec ans(q);
    for(int i=0;i<q;i++){
        int now_r = v[i].r;
        for(int j=before_r;j<=now_r;j++){
            update(seg, x, j);
        }
        /*
        for(int j=0;j<=n;j++){
            ll value = seg.getsum(j, j + 1);
            pe(value);
        }
        el;
        */
        before_r = now_r + 1;
        int now_l = v[i].l;
        ll ansvalue = seg.getsum(now_l, now_r + 1);
        ans[v[i].id] = v[i].r - v[i].l + 1 - ansvalue;
    }
    for(int i=0;i<q;i++){
        p(ans[i]);
    }

    return;
}

int main() {
    // init();
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll q, testcase = 1;

    if (multicase) {
        cin >> q;
    } else {
        q = 1;
    }
    while (q--) {
        // pu("Case ");pu("#");pu(testcase);pu(": ");
        solve();
        testcase++;
    }
    // solve();
    return 0;
}



Measured memory_bytes: 41548