#include <bits/stdc++.h> 
using namespace std; 
#define N 500002 
#define ll long long int   
// Given Array 
int arr[N],p[N]; 
// wavelet tree class 
#define ff(i,n) for(i=0;i<n;i++)
#define pb push_back
class wavelet_tree { 
public: 
    // Range to elements 
    int low, high; 
  
    // Left and Right child 
    wavelet_tree* l, *r; 
  
    vector<int> freq; 
  
    // Default constructor 
    // Array is in range [x, y] 
    // Indices are in range [from, to] 
    wavelet_tree(int* from, int* to, int x, int y) 
    { 
        // Initialising low and high 
        low = x, high = y; 
  
        // Array is of 0 length 
        if (from >= to) 
            return; 
  
        // Array is homogenous 
        // Example : 1 1 1 1 1 
        if (high == low) { 
            // Assigning storage to freq array 
            freq.reserve(to - from + 1); 
  
            // Initialising the Freq array 
            freq.push_back(0); 
  
            // Assigning values 
            for (auto it = from; it != to; it++)  
              
                // freq will be increasing as there'll 
                // be no further sub-tree 
                freq.push_back(freq.back() + 1); 
              
            return; 
        } 
  
        // Computing mid 
        int mid = (low + high) / 2; 
  
        // Lambda function to check if a number 
        // is less than or equal to mid 
        auto lessThanMid = [mid](int x) { 
            return x <= mid; 
        }; 
  
        // Assigning storage to freq array 
        freq.reserve(to - from + 1); 
  
        // Initialising the freq array 
        freq.push_back(0); 
  
        // Assigning value to freq array 
        for (auto it = from; it != to; it++)  
  
            // If lessThanMid returns 1(true), we add 
            // 1 to previous entry. Otherwise, we add 0 
            // (element goes to right sub-tree) 
            freq.push_back(freq.back() + lessThanMid(*it));         
  
        // std::stable_partition partitions the array w.r.t Mid 
        auto pivot = stable_partition(from, to, lessThanMid); 
  
        // Left sub-tree's object 
        l = new wavelet_tree(from, pivot, low, mid); 
  
        // Right sub-tree's object 
        r = new wavelet_tree(pivot, to, mid + 1, high); 
    } 
  
    // Count of numbers in range[L..R] less than  
    // or equal to k 
    int kOrLess(int l, int r, int k) 
    { 
        // No elements int range is less than k 
        if (l > r or k < low) 
            return 0; 
  
        // All elements in the range are less than k 
        if (high <= k) 
            return r - l + 1; 
  
        // Computing LtCount and RtCount 
        int LtCount = freq[l - 1]; 
        int RtCount = freq[r]; 
  
        // Answer is (no. of element <= k) in 
        // left + (those <= k) in right 
        return (this->l->kOrLess(LtCount + 1, RtCount, k) +  
             this->r->kOrLess(l - LtCount, r - RtCount, k)); 
    } 
  
}; 
void dfs(ll i,vector<vector<ll> >&vec,ll p[],ll d[],ll dis)
{
	d[i] = dis;
	ll j;
	for(j=0;j<vec[i].size();j++)
	{
		if(vec[i][j]!=p[i])
		{
			dfs(vec[i][j],vec,p,d,dis+1);
		}
	}
}
// Driver code 
int main() 
{ 
    ll t;
	t=1;
	while(t--)
	{
		ll i,n,q;
		cin>>n>>q;
	    ll a[n];
		ff(i,n)
			scanf("%lld",&a[i]);
		ll ans = 0;
		if(0)
		{
			cout<<"1";
		}
		else
		{
			int arr[n],brr[n],pos[n+1];
			ff(i,n+1)
			{		
				pos[i] = N;
			}
			ff(i,n)
			   arr[i] = a[i];	
			for(i=n-1;i>=0;i--)
			{
				brr[i] = pos[arr[i]];
				pos[arr[i]] = i;	
			}
			wavelet_tree obj(brr, brr+n, 1, N);
			int ans = 0,n1 = n;
			while(q--)
			{
			         int l,r;
			         scanf("%d %d",&l,&r);
			         ans = obj.kOrLess(l, r, r-1) ;
                     ans = (r-l+1) - ans;
                     printf("%d\n",ans);
			}
		}
    }
    return 0; 
} 

Measured memory_bytes: 138104