#include <bits/stdc++.h> 
using namespace std; 
#define in(x) int x; cin>>x;
#define sin(s) string s; cin>>s;
#define ll long long int 
#define lin(x) ll x; cin>>x;
#define vi vector<int>
#define vll vector<ll>
#define si set<int>
#define pb push_back
#define re(i,n) for(ll i=0; i<n; i++)
#define pe(i,a,b) for(ll i=a; i<=b; i++)
#define rre(i,n) for(int i=n-1; i>-1; i--) 
#define mp make_pair
#define pii pair<ll,ll>
#define endl "\n"
#define pi 3.1415926536 
#define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define fio freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
#define mod 1000000007
#define inf INT_MAX
/////////////////////////////////////////////////////////////////////////////////

bool compare(const pair<int, int>&i, const pair<int, int>&j) 
{ 
        if(i.second==j.second)
                return i.first>j.first;
        return i.second> j.second; 
} 
/////////////////////////////////////////////////////////////////////////////////
//vi v;
int ncr(int n, int k)   
{   
        if(n<k)
                return 0;
        int C[n + 1][k + 1];   
        int i, j;   
        for (i = 0; i <= n; i++)   
        {   
                for (j = 0; j <= min(i, k); j++)   
                {   
                        if (j == 0 || j == i)   
                                C[i][j] = 1;   
                        else  
                                C[i][j] = (C[i - 1][j - 1] + C[i - 1][j])%mod;   
                }   
        }   
        return C[n][k];   
} 
////////////////////////////////////////////////////////////////////////////
ll modpowIter(ll a, ll b, ll c)   
{   
        int ans=1;  
        while(b != 0)   
        {  
                if(b%2 == 1) 
                ans=(ans*a)%c;  
                a=(a*a)%c;  
                b /= 2;   
        }  
        return ans;  
} 
///////////////////////////////////////////////////////////////////////////////
string intobin(int n)
{
        string s="";
        if(n==0)
                s="0";
        while(n)
        {
                if(n%2)
                        s="1"+s;
                else
                        s="0"+s;
                n/=2;
        }
        return s;
}

////////////////////////////////////////////////////////////////////////////////

int bintoin(string s)
{
        ll n=0;
        vll v;
        v.pb(1);
        re(i,400)
        {
                v.pb((v[v.size()-1]*2)%1000003);
        }
        rre(i,s.length())
        {
                n=(n+(s[i]-'0')*v[s.length()-i-1])%1000003;
                //cout<<v[s.length()-i-1]<<endl;
        }
        return n;
}
//////////////////////////////////////////////////////////////////////////////////
ll nc2(ll n, ll k)
{
        if(n<k)
                return 0;
        return (n*(n-1))/2;
}
///////////////////////////////////////////////////////////////////////////////////
bool prime[1000001]; 
void SieveOfEratosthenes(int n)   
{     
        memset(prime, true, sizeof(prime));   
        for (int p=2; p*p<=n; p++)   
        {    
                if (prime[p] == true)   
                {   
                        for (int i=p*p; i<=n; i += p)   
                        prime[i] = false;   
                }   
        }   
        /*for (int p=2; p<=n; p++)   
                if (prime[p])   
                        v.pb(p);  */
}   
////////////////////////////////////////////////////////////////////////////////////

const int MAX = 1000001; 
  
// structure to store queries 
struct Query 
{ 
    int 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(int idx, int val, int bit[], int n) 
{ 
    for (; idx <= n; idx += idx&-idx) 
        bit[idx] += val; 
} 
  
// querying the bit array 
int query(int idx, int bit[], int n) 
{ 
    int sum = 0; 
    for (; idx>0; idx-=idx&-idx) 
        sum += bit[idx]; 
    return sum; 
} 
  
void answeringQueries(int arr[], int n, Query queries[], int q) 
{ 
    // initialising bit array 
    int 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 
    int last_visit[MAX]; 
    memset(last_visit, -1, sizeof(last_visit)); 
  
    // answer for each query 
    int ans[q]; 
    int query_counter = 0; 
    for (int 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++; 
        } 
    } 
  
    // print answer for each query 
    for (int i=0; i<q; i++) 
        cout << ans[i] << endl; 
} 
int main()
{
        FAST
        in(n)
        in(q)
        int arr[n];
        re(i,n)
        cin>>arr[i];
        Query queries[q]; 
        re(i,q)
        {
                in(x)
                in(y)
                x--;
          		y--;
                queries[i].l=x;
                queries[i].r=y;
                queries[i].idx=i;
        }
        sort(queries, queries+q, cmp); 
        answeringQueries(arr, n, queries, q); 
        return 0;
}

Measured memory_bytes: 19340