a.cpp

#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
using ll = long long;
const int MOD = 998244353;
const int MAXN = 2e5 + 10;

pair <pair <int, int>, pair <int, int> > b[MAXN];
int a[MAXN], k, cnt[MAXN], ans[MAXN];

void add(int x){
    cnt[x]++;
    if (cnt[x] == 1){
        k++;
    }
}


void del(int x){
    cnt[x]--;
    if (cnt[x] == 0){
        k--;
    }
}

void solve() {

    int n, q;
    cin >> n >> q;
    for (int i = 0; i < n; i++){
        cin >> a[i];
    }
    int len = sqrt(n);
    for (int i = 0; i < q; i++){
        int l, r;
        cin >> l >> r;
        l--;
        r--;
        b[i].f.f = l / len;
        b[i].f.s = r;
        b[i].s.f = l;
        b[i].s.s = i;
    }

    sort (b, b + q);

    int left = 0;
    int right = -1;
    k = 0;

    for (int i = 0; i < q; i++){

        while (right < b[i].f.s){
            right++;
            add(a[right]);
        }
        while (left > b[i].s.f){
            left--;
            add(a[left]);
        }
        while (right > b[i].f.s){
            del(a[right]);
            right--;
        }
        while(left < b[i].s.f){
            del(a[left]);
            left++;
        }
        ans[b[i].s.s] = k;
    }

    for (int i = 0; i < q; i++){
        cout << ans[i] << '\n';
    }

}

int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr); std::cout.tie(nullptr);
    int t = 1;
    //cin >> t;
    while (t--) {
        solve();
    }
}