#include <stdio.h>
#include <math.h>
#include <algorithm>
#include <vector>

using namespace std;

int m[100010]; // da li posotji autor sa brojem I i koji je po redu zapamcen
int p[100010][2]; // prvo i poslednje pojavljivanje i-tog autora (ali naseg i-tog, ne sa brojem i)
int r[10010][10010]; // br razl autora od i-tog do j-tog clana
int niz[100010]; //raspored knjiga
int n,k;

bool imaDoSad(int i, int j, int t)
{
     if(p[m[t]][0]>j || p[m[t]][1]<i) return false;
     return true;
}

int main()
{
    FILE *f,*g;
    f=fopen("knjige.in","r");
    g=fopen("knjige.out","w");
    
    int a=0,i=0, t=1, j=0, d=0;
    fscanf(f,"%d %d", &n, &k);
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=n;j++)
          r[i][j]=0;
        m[i]=-1;
        p[i][0]=p[i][1]=0;
        r[i][i]=1;
    }
    
    for(i=1;i<=n;i++)
    {
       fscanf(f,"%d",&a);
       niz[i]=a;
       if(m[a]==-1)
       {
         m[a]=t; // broj autora a se nalazi na t-tom mestu u nasem nizu p
         p[t][0]=p[t][1]=i;
         t++;
       }
       else
           p[m[a]][1]=i;
    }
    
    for(d=2;d<=n;d++)
      for(i=1;i<=n-d+1;i++)
      {
          j=i+d-1;
          for(t=i+1;t<=j;t++)
          {
              if(imaDoSad(i,t-1,niz[t]))
                  r[i][t]=r[i][t-1];
              else r[i][t]=r[i][t-1]+1;
          }
      }
    
    for(t=0;t<k;t++)
    {
       fscanf(f, "%d %d",&i, &j);
       fprintf(g,"%d\n", r[i][j]); 
    }
    
    fclose(f);
    fclose(g);
}
