#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <vector>
using namespace std;
int Max,KT[61][100010],i,j,n,k,a[100010],x,y,res,pom;
vector <int> Vektor[100010];
FILE *f;
FILE *g;
void add(int pos,int red)
{
    int i=pos;
    while (i<=Max)
    {
        KT[red][i]++;
        i+=(i&(i^(i-1)));
    }
}
int sum (int pos,int red)
{
    int suma,i=pos;
    suma=0;
    while (i>0)
    {
        suma+=KT[red][i];
        i-=(i&(i^(i-1)));
    }
    return suma;
}
bool search(int broj,int op1, int op2)
{
    bool p=false;
    int l=0,r=Vektor[broj].size() -1, s;
    while ((l<=r) && (!p))
    {
        s=(l+r)/2;
        if ((Vektor[broj][s]<=op2) && (Vektor[broj][s]>=op1)) p=true;
        else if (Vektor[broj][s]>op2) r=s-1;
        else l=s+1;
    }
    return p;
}
int main()
{
    f=fopen("knjige.in","r");
    g=fopen("knjige.out","w");
    fscanf(f,"%d%d",&n,&k);Max=0;
    for (i=0;i<n;i++) {fscanf(f,"%d",&a[i]); if (a[i]>Max) Max=a[i];}
    if (Max<=60)
    {
    memset(KT,0,sizeof(KT));
    for (i=0;i<n;i++) add(i+1,a[i]-1);
    for (i=0;i<k;i++)
    {
        fscanf(f,"%d%d",&x,&y);
        res=0;
        for (j=1;j<=Max;j++)
        {
            pom=sum(y,j-1);
            if (x>1) pom-=sum(x-1,j-1);
            if (pom>0) res++;
        }
        fprintf(g,"%d\n",res);
    }
    }
    else
    {
        for (j=1;j<=Max;j++) Vektor[j].clear();
        for (i=0;i<n;i++) Vektor[a[i]].push_back(i+1);
        for (i=0;i<k;i++)
        {
            fscanf(f,"%d%d",&x,&y);
            res=0;
            for (j=1;j<=Max;j++)
            {
                if (search(j,x,y)) res++;
            }
            fprintf(g,"%d\n",res);
        }
    }
    fclose(f);
    fclose(g);
    return 0;
}
