#include <iostream>
#include <stdio.h>
#include <cstring>
#include <vector>
using namespace std;

#define pb push_back

#define MaxN 10000

int n,m;
int a[MaxN];
int najv;
vector<int> p[MaxN];
int p1,p2;
int ret;
bool mark[MaxN];

bool BinarySearch( int j, int p1, int p2 )
{

    int l = 0;
    int h = p[j].size();
    int mid;

    while ( h - l > 0 ) {

        mid = ( h + l ) / 2;

        if ( p[j][mid] < p1 ) l = mid+1;
        else                  h = mid;

    }

    if ( l == p[j].size() ) return false;
    if ( p[j][l] > p2 ) return false;

    return true;

}

int main()
{

    freopen("knjige.in","r",stdin);
    freopen("knjige.out","w",stdout);

    memset(mark, 0, sizeof(mark));
    scanf("%d%d",&n,&m);
    najv = 0;
    int br = 0;
    for (int i = 0; i < n; i++) {
       scanf("%d",&a[i]);
       a[i]--;
       najv = max(najv,a[i]);
       p[ a[i] ].pb( i );
    }

    if ( n <= 2000 ) {
        for (int i = 0; i < m; i++) {
            scanf("%d%d",&p1,&p2);
            p1--; p2--;

            for (int j = 0; j < 2000; j++)
               mark[ j ] = false;
            ret = 0;
            for (int j = p1; j <= p2; j++)
               if ( !mark[ a[ j ] ] ) {
                  mark[ a[j] ] = true;
                  ret++;
               }

            printf("%d\n",ret);
        }
    }
    else {
        for (int i = 0; i < m; i++) {
            scanf("%d%d",&p1,&p2);
            p1--; p2--;

            ret = 0;
            for (int j = 0; j <= najv; j++)
                if ( BinarySearch( j, p1, p2 ) ) ret++;
            printf("%d\n",ret);
        }
    }

    fclose(stdin);
    fclose(stdout);

    return 0;
}
