a.cpp

#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;
const int MAXN = 2e5 + 10;
int a[MAXN], cnt_val[MAXN], cnt;
pair <pair <int, int>, pair <int, int> > b[MAXN];
void add(int pos){
    cnt_val[a[pos]]++;
    if (cnt_val[a[pos]] == 1){
        cnt++;
    }
}
void del(int pos){
    cnt_val[a[pos]]--;
    if (cnt_val[a[pos]] == 0){
        cnt--;
    }
}
int main()
{
    int n, m;
    cin >> n >> m;

    for (int i = 0; i < n; i++){
        cin >> a[i];
    }
    int len = sqrt(n);
    for (int i = 0; i < m; i++){
        int l, r;
        cin >> 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 + m);
    int left, right;
    left = 0;
    right = -1;
    ans = 0;
    cnt = 0;
    for (int i = 0; i < m; i++){
        while (right < b[i].f.s){
            right++;
            add(right);
        }
        while (left > b[i].s.f){
            left--;
            add(left);
        }
        while (right > b[i].f.s){
            del(right);
            right--;
        }

        while (left < b[i].s.f){
            del(left);
            left++;
        }
        ans[b[i].s.s] = cnt;
    }


    return 0;
}