#include <bits/stdc++.h>
using namespace std;
#define fio ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
#define ll long long
#define dd double
#define pb push_back
#define ff first
#define ss second
#define Mp make_pair
const ll Mod=1000000007;
const ll INF=999999999999999999;
const ll NN=(ll)(1e6+5);
ll min(ll x,ll y){if(x<y) return x;return y;}
ll max(ll x,ll y){if(x>y) return x;return y;}
ll power(ll x,unsigned ll y) 
{ 
    if (y==0) 
        return 1; 
    else if (y%2==0) 
        return power(x,y/2)*power(x,y/2); 
    else
        return x*power(x,y/2)*power(x,y/2); 
}
ll hcf(ll a,ll b) 
{ 
    if(b==0) 
        return a; 
    return hcf(b,a%b);  
}
//Reference:https://www.geeksforgeeks.org/queries-number-distinct-elements-subarray/
const ll MAX = (ll)(1e6+5); 
// structure to store queries 
struct Query 
{ 
    ll l, r, idx; 
}; 
  
// cmp function to sort queries according to r 
bool cmp(Query x, Query y) 
{ 
    return x.r < y.r; 
} 
  
// updating the bit array 
void update(ll idx, ll val, ll bit[], ll n) 
{ 
    for (; idx <= n; idx += idx&-idx) 
        bit[idx] += val; 
} 
  
// querying the bit array 
ll query(ll idx, ll bit[], ll n) 
{ 
    ll sum = 0; 
    for (; idx>0; idx-=idx&-idx) 
        sum += bit[idx]; 
    return sum; 
} 
  
void answeringQueries(ll arr[], ll n, Query queries[], ll q) 
{ 
    // initialising bit array 
    ll bit[n+1]; 
    memset(bit, 0, sizeof(bit)); 
  
    // holds the rightmost index of any number 
    // as numbers of a[i] are less than or equal to 10^6 
    ll last_visit[MAX]; 
    memset(last_visit, -1, sizeof(last_visit)); 
  
    // answer for each query 
    ll ans[q]; 
    ll query_counter = 0; 
    for (ll i=0; i<n; i++) 
    { 
        // If last visit is not -1 update -1 at the 
        // idx equal to last_visit[arr[i]] 
        if (last_visit[arr[i]] !=-1) 
            update (last_visit[arr[i]] + 1, -1, bit, n); 
  
        // Setting last_visit[arr[i]] as i and updating 
        // the bit array accordingly 
        last_visit[arr[i]] = i; 
        update(i + 1, 1, bit, n); 
  
        // If i is equal to r of any query  store answer 
        // for that query in ans[] 
        while (query_counter < q && queries[query_counter].r == i) 
        { 
            ans[queries[query_counter].idx] = 
                     query(queries[query_counter].r + 1, bit, n)- 
                     query(queries[query_counter].l, bit, n); 
            query_counter++; 
        } 
    } 
  
    // prll answer for each query 
    for (ll i=0; i<q; i++) 
        cout << ans[i] << "\n"; 
}  
int main()
{
   fio;
   /*#ifndef ONLINE_JUDGE 
    	freopen("input.txt", "r", stdin); 
    	freopen("output.txt", "w", stdout); 
    	freopen("error.txt", "w", stderr); 
   #endif*/
   ll TT=1;
   //cin>>TT;
   while(TT--)
   {
       ll n,i,q,x,y;
       cin>>n>>q;
       ll a[n];
       for(i=0;i<n;i++)
        cin>>a[i];
       Query queries[q];
       for(i=0;i<q;i++)
       {
           cin>>x>>y;
           queries[i].l=x-1;
           queries[i].r=y-1;
           queries[i].idx=i;
       } 
       sort(queries,queries+q,cmp);
       answeringQueries(a, n, queries, q); 
   }
   return 0;
}

Measured memory_bytes: 35100