// itne me hi thakk gaye?
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize ("-O3")
#define ll long long 
#define ull unsigned long long
using ld = long double;
const ll mod = 1e9 + 7;
const ll inf = 1e18;
const ll rk = 256;
const ll mod2 = 998244353;
const ld PI = 3.141592653589793;
#define pb push_back
#define mp make_pair
#define vc vector
#define fs first
#define sec second
#define pq priority_queue
#define lb lower_bound
#define ub upper_bound
#define pll pair<ll,ll> 
#define pls pair<ll,string>
#define psl pair<string,ll>
#define plc pair<ll,char>
#define pcl pair<char,ll>
#define pss pair<string,string>
#define all(x) (x).begin(), (x).end()
#define tol(s) transform(s.begin(),s.end(),s.begin(),::tolower);
#define tou(s) transform(s.begin(),s.end(),s.begin(),::toupper);
#define print(a) for(auto j:a) {cout<<j<<",";} cout << "\n";
#define endl '\n'
#define whatis(x) cout << "> "<<#x << " ==> " << x << endl;
#define lwi(x) cout << " your " << #x << " is ---> " << x << " ";
#define FastIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
 
// // Printing pair
ostream & operator << (ostream & os, pair <ll, ll> const& x) {
    os << x.first << "," << x.second;
    return os;
}
 
// printing vector
template <class T>
ostream & operator << (ostream & os, vector <T> const& x) {
    os << "{ ";
    for(auto& y : x) os << y << " ";
    return os << "}";
}
 
// printing set
template <class T>
ostream & operator << (ostream & os, set <T> const& x) {
    os << "{ ";
    for(auto& y : x) os << y << " ";
    return os << "}";
}
 
template <class Ch, class Tr, class Container>
basic_ostream <Ch, Tr> & operator << (basic_ostream <Ch, Tr> & os, Container const& x) {
    os << "{ ";
    for(auto& y : x) os << y << " ";
    return os << "}";
}
 
template <class X, class Y>
ostream & operator << (ostream & os, pair <X, Y> const& p) {
    return os << "[ " << p.first << ", " << p.second << "]" ;
}
const int MAX = 1000001; 
  
struct Query 
{ 
    int l, r, idx; 
}; 
bool comp_s(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 solve(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(){
    FastIO;
    int n, q;
    cin >> n >> q;
    int a[n];
    for(int i=0; i<n; i++) cin >> a[i];
    Query queries[q];
    for(int i=0; i<q; i++) {
        int a, b;
        cin >> a >> b;
        queries[i].l = a-1;
        queries[i].r = b-1;
        queries[i].idx = i;
    }
    sort(queries, queries+q, comp_s); 
    solve(a, n, queries, q); 
    return 0;
}


Measured memory_bytes: 19380