#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define MOD3 1000000000
#define MOD2 998244353 
float PHI = 1.6180339;
const float  PI_F=3.14159265358979f;
//#define MAX 1000 m
#define endl "\n"    
#define manhunt 32 
#define all(v) (v).begin(),(v).end()
#define sz(v) ((int)(v).size())
#define pi 3.1415926535897932384626433
//typedef long long float;
#define int long long
//#define double long double
typedef pair<int, int> pii;
//#define float unsigned long long
#define FAST ios_base::sync_with_stdio(false);cin.tie();cout.tie();
#define CHAR_SIZE 26 
const int MAX = 1000001; 

int modpow(int x, int n, int m) { if (n == 0) return 1%m; long long u = modpow(x,n/2,m); u = (u*u)%m; if (n%2 == 1) u = (u*x)%m; return u; } 


int add(int x, int y,int m) 
{
	x += y;
	if (x >= m) return x - m;
	return x;
}
int sub(int x, int y) 
{
	x -= y;
	if (x < 0) return x + MOD;
	return x;
}
int inv(int a, int m = MOD2)
{
	return modpow(a, m - 2, m);
}
int mul(int a, int b,int m) 
{
	return (long long) a * b % m;
}


int nCrModp(int n, int r, int p) 
{ 
    int C[r+1]; 
    memset(C, 0, sizeof(C)); 
  
    C[0] = 1; 
    for (int i = 1; i <= n; i++) 
    { 
        for (int j = min(i, r); j > 0; j--) 
            C[j] = (C[j] + C[j-1])%p; 
    } 
    return C[r]; 
} 

bool sortinrev(const pair<int,int> &a,  
               const pair<int,int> &b) 
{ 
    if(a.first==b.first)
    return a.second<b.second;
      return (a.first > b.first); 
       //return (a.first-a.second)>(b.first-b.second);
}

vector<int> z_function(string &s)
{
	int n=s.size();
	vector<int> z(n);
	for(int i=1,l=0,r=0;i<n;i++)
	{
		if(i<=r)
			z[i]=min(r-i+1, z[i-l]);
		while(i+z[i]<n && s[z[i]]==s[i+z[i]])
			z[i]++;
		if(i+z[i]-1>r)
			l=i, r=i+z[i]-1;
	}
	return z;
}

bool isprime(int n) 
{ 
    if (n <= 1)  return false; 
  
    for (int i=2; i*i<=n; i++) 
        if (n%i == 0) 
            return false; 
  
    return true; 
}

void SieveOfEratosthenes(int n, bool isPrime[]) 
{ 
    isPrime[0] = isPrime[1] = false; 
    for (int i=2; i<=n; i++) 
        isPrime[i] = true; 
  
    for (int p=2; p*p<=n; p++) 
    { 
        if (isPrime[p] == true) 
        { 
            for (int i=p*p; i<=n; i += p) 
                isPrime[i] = false; 
        } 
    } 
}
//reference from https://www.geeksforgeeks.org/queries-number-distinct-elements-subarray/
struct Query 
{ 
    int l, r, idx; 
}; 

bool cmp(Query x, Query y) 
{ 
    return x.r < y.r; 
} 

void update(int idx, int val, int bit[], int n) 
{ 
    for (; idx <= n; idx += idx&-idx) 
        bit[idx] += val; 
} 

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) 
{ 
    int bit[n+1]; 
    memset(bit, 0, sizeof(bit)); 

    int last_visit[MAX]; 
    memset(last_visit, -1, sizeof(last_visit)); 

    int ans[q]; 
    int query_counter = 0; 
    for (int i=0; i<n; i++) 
    { 
        if (last_visit[arr[i]] !=-1) 
            update (last_visit[arr[i]] + 1, -1, bit, n); 

        last_visit[arr[i]] = i; 
        update(i + 1, 1, bit, n); 

        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++; 
        } 
    } 

    for (int i=0; i<q; i++) 
        cout << ans[i] << endl; 
} 



int32_t main()
{
    /* freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout); */
    FAST
    cout << fixed << setprecision(16);
    
    int n,q;
    cin>>n>>q;
    int arr[n+10];
    for(int i=0;i<n;i++)
    {
        cin>>arr[i];
    }
    vector<pii>v;
    Query queries[q+10]; 
    for(int i=0;i<q;i++)
    {
        int a,b;
        cin>>a>>b;
        --a;
        --b;
        v.push_back({a,b});
        queries[i].l=a;
        queries[i].r=b;
        queries[i].idx=i;
    }
    sort(v.begin(),v.end());
    sort(queries, queries+q, cmp); 
    for(int i=0;i<q;i++)
    {
        int l=v[i].first;
        int r=v[i].second;
    }
    answeringQueries(arr, n, queries, q);
    
    return 0;
}





Measured memory_bytes: 43056