#include<bits/stdc++.h>
#define MOD 1000000007
#define md 998244353
#define INF LLONG_MAX
#define F first
#define S second
#define sz(x) (long long)x.size()
#define vi vector<int>
#define vll vector<long long>
#define vpl vector<pair<long long,long long> >
#define vpi vector<pair<int,int> >
#define pb push_back
#define debug(x) cerr<<#x<<"= "<<x<<endl
#define all(v) v.begin(),v.end()
#define TT ll test;cin>>test; while(test--)
#define rep(i,a,n) for(ll i=a;i<(long long)n;++i)
#define repr(i,n,a) for(ll i=n;i>(long long)a;--i)
#define endl '\n'
#define MAXN 100005
typedef long long ll;
typedef long double ld;
using namespace std;
#define int long long int
const int MAX = 500005; 
  
// Variable to represent block size. This is made 
// global so compare() of sort can use it. 
int block; 
  
// Structure to represent a query range and to store 
// index and result of a particular query range 
struct Query { 
    int L, R, index, result; 
}; 
  
// Function used to sort all queries so that all queries 
// of same block are arranged together and within a block, 
// queries are sorted in increasing order of R values. 
bool compare(Query x, Query y) 
{ 
    // Different blocks, sort by block. 
    if (x.L / block != y.L / block) 
        return x.L / block < y.L / block; 
  
    // Same block, sort by R value 
    return x.R < y.R; 
} 
  
// Function used to sort all queries in order of their 
// index value so that results of queries can be printed 
// in same order as of input 
bool compare1(Query x, Query y) 
{ 
    return x.index < y.index; 
} 
  
// calculate distinct elements of all query ranges. 
// m is number of queries n is size of array a[]. 
void queryResults(int a[], int n, Query q[], int m) 
{ 
    // Find block size 
    block = (int)sqrt(n); 
  
    // Sort all queries so that queries of same 
    // blocks are arranged together. 
    sort(q, q + m, compare); 
  
    // Initialize current L, current R and current 
    // different elements 
    int currL = 0, currR = 0; 
    int curr_Diff_elements = 0; 
  
    // Initialize frequency array with 0 
    int* freq = new int[MAX]; 
  	memset(freq,0,MAX);
    // Traverse through all queries 
    for (int i = 0; i < m; i++) { 
          
        // L and R values of current range 
        int L = q[i].L, R = q[i].R; 
  
        // Remove extra elements of previous range. 
        // For example if previous range is [0, 3] 
        // and current range is [2, 5], then a[0]  
        // and a[1] are subtracted 
        while (currL < L) { 
              
            // element a[currL] is removed 
            freq[a[currL]]--; 
            if (freq[a[currL]] == 0)  
                curr_Diff_elements--; 
              
            currL++; 
        } 
  
        // Add Elements of current Range 
        // Note:- during addition of the left 
        // side elements we have to add currL-1 
        // because currL is already in range 
        while (currL > L) { 
            freq[a[currL - 1]]++; 
  
            // include a element if it occurs first time 
            if (freq[a[currL - 1]] == 1)  
                curr_Diff_elements++; 
              
            currL--; 
        } 
        while (currR <= R) { 
            freq[a[currR]]++; 
  
            // include a element if it occurs first time 
            if (freq[a[currR]] == 1)  
                curr_Diff_elements++; 
              
            currR++; 
        } 
  
        // Remove elements of previous range. For example 
        // when previous range is [0, 10] and current range 
        // is [3, 8], then a[9] and a[10] are subtracted 
        // Note:- Basically for a previous query L to R 
        // currL is L and currR is R+1. So during removal 
        // of currR remove currR-1 because currR was 
        // never included 
        while (currR > R + 1) { 
  
            // element a[currL] is removed 
            freq[a[currR - 1]]--; 
  
            // if occurrence of a number is reduced 
            // to zero remove it from list of  
            // different elements 
            if (freq[a[currR - 1]] == 0)  
                curr_Diff_elements--; 
              
            currR--; 
        } 
        q[i].result = curr_Diff_elements; 
    } 
} 
  
// print the result of all range queries in 
// initial order of queries 
void printResults(Query q[], int m) 
{ 
    sort(q, q + m, compare1); 
    for (int i = 0; i < m; i++) { 
        cout << q[i].result << endl; 
    } 
} 
signed main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    ll n,q;
    cin>>n>>q;
    ll a[n];
    for (int i = 0; i < n; ++i)
    {
        cin>>a[i];
    }
    Query* Q= new Query[q];
    for (int i = 0; i < q; ++i)
    {
        ll x,y;
        cin>>x>>y;--x;--y;
        Q[i]={x,y,i,0};
    }
    queryResults(a,n,Q,q);
    printResults(Q,q);
    return 0;
}

Measured memory_bytes: 27224