#include <stdio.h>
#include <algorithm>
using namespace std;

#define MaxBr 100010

int n,a[100100],zad[100100],res[100100],c[100100];

struct interval {
    int p,k,pos;
};

interval v[100100];

bool cmp(interval a, interval b) {
    return (a.k < b.k || (a.k==b.k && a.p < b.p));
}

void add(int x, int p) {
    int xp;
    for(xp=x; xp<=n; xp+=xp&(-xp)) c[xp]+=p;
}

int sum(int x) {
    int s,xp;
    s=0;
    for(xp=x; xp>0; xp-=xp&(-xp)) s+=c[xp];
    return s;
}

int main() {

    int m,i,p,t;
    FILE *ff=fopen("knjige.in","r"), *gg=fopen("knjige.out","w");

    fscanf(ff,"%d%d", &n, &m);

    for(i=1; i<=n; i++) fscanf(ff,"%d",&a[i]);
    for(i=0; i<m; i++) {
        fscanf(ff,"%d%d", &v[i].p, &v[i].k);
        v[i].pos=i;
    }

    sort(v,v+m,cmp);
    for(i=0; i<=MaxBr; i++) {
        zad[i]=-1;
        c[i]=0;
    }

    p=0;
    for(i=0; i<m; i++) {
        while( p < v[i].k ) {
            p++;
            t=a[p];
            if (zad[t]!=-1) add(zad[t],-1);
            add(p,1);
            zad[t]=p;
        }
        res[v[i].pos]=sum(v[i].k)-sum(v[i].p-1);
    }

    for(i=0; i<m; i++) fprintf(gg,"%d\n", res[i]);
    fclose(ff); fclose(gg);
    return 0;
}
