#include <cstdio>
#include <algorithm>
int n,k,a,b;

int cum[300000];
int pre[100002];
int dp[100002];
void updatec(int idx, int v)
{
    while ( idx<=n)
    {
        cum[idx]+=v;
        idx+=idx&-idx;
    }
}
int readc( int idx)
{
    int r=0;
    while ( idx>0)
    {
        r+=cum[idx];
        idx-=idx&-idx;
    }
    return r;
}
int ukupno=0;
struct T
{
    int a,b;
} upiti[100002];
int res[100002];
bool cmp ( int t1, int t2)
{
    return upiti[t1].b< upiti[t2].b;
}

int rasp[100002];
int niz[100002];
int main()
{
    //freopen("input.txt","r",stdin);
    scanf("%d %d",&n,&k);

    for ( int i=1;i<=n;i++)
        scanf("%d",niz+i);

    for ( int i=0;i<k;i++,rasp[i]=i)
        scanf("%d %d",&upiti[i].a,&upiti[i].b);

    std::sort(rasp,rasp+k,cmp);

    int p=0;
    for ( int i=0;i<k;i++)
    {

        if ( upiti[rasp[i]].b != p )
        {
            for ( int j=p+1;j<=upiti[rasp[i]].b;j++)
            {
                dp[j]=dp[j-1];
                if ( pre[niz[j]]==0 )
                {
                    dp[j]++;
                    pre[niz[j]]=j;
                    updatec(pre[niz[j]]+1,1);
                    updatec(j+1,-1);
                }
            }
        }
        p=upiti[rasp[i]].b;
        res[rasp[i]]=dp[upiti[rasp[i]].b]-dp[upiti[rasp[i]].a-1]+ readc( upiti[rasp[i]].a);
    }
    for ( int i=0;i<k;i++)
    printf("%d\n",res[i]);
    return 0;
}
