# include <iostream>
# include <algorithm>
# include <cstdio>
# include <cstring>

using namespace std;

const int MaxN = 1 << 17;

struct Segment {
       int tree[2 * MaxN - 1];
       
       void init() {
            memset( tree, 0, sizeof( tree ) );
       }
       
       void update( int pos, int by ) {
            pos += MaxN - 1;
            tree[pos] += by;
            while ( pos > 0 ) {
                  pos = ( pos - 1 ) / 2;
                  tree[pos] += by;
            }
       }
       
       int getSum( int node, int low, int high, int nlow, int nhigh ) {
           if ( nlow > high || nhigh < low ) return 0;
           if ( low >= nlow && high <= nhigh ) return tree[node];
           
           int res = 0;
           int mid = ( low + high ) / 2;
           res += getSum( node * 2 + 1, low, mid, nlow, nhigh );
           res += getSum( node * 2 + 2, mid + 1, high, nlow, nhigh );
           
           return res;
       }
       
       int get( int sta, int end ) {
           return getSum( 0, 0, MaxN - 1, sta, end );
       }
} segment;

struct Interval {
       int sta;
       int end;
       int idx;
       
       bool operator<( const Interval& other ) const {
            return end < other.end;
       }
};

int n;
int k;
int arr[MaxN];
Interval intervals[MaxN];

int last[MaxN];
int res[MaxN];

int main() {
    freopen( "knjige.in", "r", stdin );
    freopen( "knjige.out", "w", stdout );
    
    scanf( "%d%d", &n, &k );
    for ( int i = 0; i < n; i++ )
        scanf( "%d", &arr[i] );
    for ( int i = 0; i < k; i++ ) {
        intervals[i].idx = i;
        scanf( "%d%d", &intervals[i].sta, &intervals[i].end );
        intervals[i].sta--;
        intervals[i].end--;
    }
        
    sort( intervals, intervals + k );
    
    int p = 0;
    segment.init();
    memset( last, -1, sizeof( last ) );
    for ( int i = 0; i < k; i++ ) {
        while ( p <= intervals[i].end ) {
              if ( last[arr[p]] > -1 )
                 segment.update( last[arr[p]], -1 );
              last[arr[p]] = p;
              segment.update( last[arr[p]], 1 );
              p++;
        }
        
        res[intervals[i].idx] = segment.get( intervals[i].sta, intervals[i].end );
    }
    
    for ( int i = 0; i < k; i++ ) printf( "%d\n", res[i] );
    
    return 0;
}
