#include <bits/stdc++.h>
using namespace std;

namespace AC {
#define ll int
#define PLL pair<ll, ll>
#define PDD pair<double, double>
#define PDPLL pair<double, PLL>
#define PLPLL pair<ll, PLL>
#define pb push_back
#define fi first
#define se second
#define ls rt << 1
#define rs rt << 1 | 1

    const ll N = 1e5 + 66;

    ll BUGS = 1;

    inline ll read(){
        ll x = 0;    bool flag = 1;   char ch = getchar();
        while(ch < '0' || ch > '9') { if(ch == '-') flag = 0; ch = getchar(); }
        while(ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + ch - '0'; ch = getchar(); }
        if(flag) return x;  return (~(x - 1));
    }

    inline void read(ll arr[], ll s, ll e) { for(ll i = s; i <= e; ++i) arr[i] = read(); }

    inline void write(ll x){
        if(x < 0) { x = ~(x - 1); putchar('-'); }
        if(x > 9) write(x / 10); putchar(x % 10 + '0');
    }

    inline void print(ll x) { write(x); puts(""); }

    inline void print(ll arr[], ll s, ll e) {
        for(ll i = s; i <= e - 1; ++i) write(arr[i]), putchar(' ');
        write(arr[e]); puts("");
    }

    inline ll max3(ll a, ll b, ll c) { return max(a, max(b, c)); }

    inline ll min3(ll a, ll b, ll c) { return min(a, min(b, c)); }

    inline void debugNum(ll num, string ss) { cout << "BUGS" << BUGS++ << " : " << ss << " : " << num << endl; }

    inline void debugArr(ll arr[], ll s, ll e, string ss) {
        cout << "BUGS" << BUGS++ << " : " << ss << " : " << endl;
        for(ll i = s; i <= e; ++i) cout << "i : " << i << " val : " << arr[i] << endl;
    }

    inline void IO() {
        //ios::sync_with_stdio(false), cout.tie(0), cin.tie(0);
        //cout << setiosflags(ios::fixed) << setprecision(1); //保留小数点后1位
        //cout << setprecision(1); //保留1位有效数字
        freopen("in.txt", "r", stdin);
        freopen("out.txt", "w", stdout);
    }
}using namespace AC;

map<ll, ll> MM;

namespace MoTeam {
    const ll MAXN = 5e5 + 66;

    struct input {
        ll ql, qr, id;
    }ds[MAXN];
    ll n, m, k, res, pos[MAXN], arr[MAXN], ans[MAXN], cnt[MAXN];

    inline void clearMoTeam() {

    }

    inline void add(ll idx) {
        if(cnt[arr[idx]] == 0) res++;
        cnt[arr[idx]]++;
    }

    inline void sub(ll idx) {
        if(cnt[arr[idx]] == 1) res--;
        cnt[arr[idx]]--;
    }

    inline void solve() {
        n = read(), m = read();
        ll siz = sqrt(n);
        for(ll i = 1; i <= n; ++i) {
            arr[i] = read();
            pos[i] = i / siz;
        }
        for(ll i = 0; i < m; ++i) {
            ds[i].ql = read();
            ds[i].qr = read();
            ds[i].id = i;
        }
        sort(ds, ds + m, [] (input it1, input it2) {
            return pos[it1.ql] == pos[it2.ql] ? it1.qr < it2.qr : pos[it1.ql] < pos[it2.ql];
        });
        ll l = 1, r = 0;
        for(ll i = 0; i < m; ++i) {
            while(ds[i].ql < l) {
                //add(--l);
                res+=!cnt[arr[--l]]++;
            }
            while(ds[i].qr > r) {
                //add(++r);
                res+=!cnt[arr[++r]]++;
            }
            while(ds[i].ql > l){
                /*if(cnt[arr[l]] == 1) res--;
                cnt[arr[l--]];*/
                res-=!--cnt[arr[l++]];
                //sub(l++);
            }
            while(ds[i].qr < r) {
                //sub(r--);
                res-=!--cnt[arr[r--]];
            }
            ans[ds[i].id] = res;
        }
        for(ll i = 0; i < m; ++i) print(ans[i]);
    }
}using namespace MoTeam;

int main() {
    //IO();
    solve();
    return 0;
}



Measured memory_bytes: 17380