#include<algorithm>
#include<cstdio>
#include<cmath>

using namespace std;

const int Q = 200005;
const int N = 30005;
int block[Q], n, q, a[N], buc[N], t[N];

struct Query{
    int l, r, id, ans;
}query[Q];

bool cmp(Query a, Query b){
    if(block[a.l] == block[b.l])    return a.r < b.r;
    return block[a.l] < block[b.l];
}

bool _cmp(Query a, Query b){
    return a.id < b.id;
}

void disc(){
    sort(t+1, t+n+1);
    int len = unique(t+1, t+n+1) - (t+1);
    for(int i = 1; i <= n; i++)
        a[i] = lower_bound(t+1, t+n+1, a[i]) - t;
}

int main(){
    scanf("%d", &n);
    scanf("%d", &q);
    for(int i = 1; i <= q; i++) block[i] = sqrt(i+0.5);
    for(int i = 1; i <= n; i++) scanf("%d", &a[i]), t[i] = a[i];
    disc();
    for(int i = 1; i <= q; i++) scanf("%d%d", &query[i].l, &query[i].r), query[i].id = i;
    sort(query+1, query+q+1, cmp);
    int l = 1, r = 1, ans = 1;
    buc[a[1]]++;
    for(int i = 1; i <= q; i++){
        while(l < query[i].l){
            buc[a[l]]--;
            if(!buc[a[l]])  ans--;
            l++;
        }
        while(l > query[i].l){
            l--;
            if(!buc[a[l]])  ans++;
            buc[a[l]]++;
        }
        while(r < query[i].r){
            r++;
            if(!buc[a[r]])  ans++;
            buc[a[r]]++;
        }
        while(r > query[i].r){
            buc[a[r]]--;
            if(!buc[a[r]])  ans--;
            r--;
        }
        query[i].ans = ans;
    }
    sort(query+1, query+q+1, _cmp);
    for(int i = 1; i <= q; i++)
        printf("%d\n", query[i].ans);
    return 0;
}