#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp> 
#include <ext/pb_ds/detail/standard_policies.hpp>
using namespace __gnu_pbds;
using namespace std;
#define getbit(n, i) (((n) & (1LL << (i))) != 0) 
#define setbit0(n, i) ((n) & (~(1LL << (i)))) 
#define setbit1(n, i) ((n) | (1LL << (i))) 
#define togglebit(n, i) ((n) ^ (1LL << (i))) 
#define lastone(n) ((n) & (-(n))) 
char gap = 32;
template<typename T> 
ostream& operator<<(ostream &os, const vector<T> &v) { 
    os << '{'; 
    for (const auto &x : v) os << gap << x;
        return os << '}'; 
}
template<typename A, typename B> 
ostream& operator<<(ostream &os, const pair<A, B> &p) {
        return os << '(' << p.first << gap << p.second << ')';
}

template <class T>
void read(T &x) {
    char c;
    for (c = getchar(); c < '0' || c > '9'; c = getchar())
        ;
    for (x = 0; c <= '9' && c >= '0'; c = getchar()) x = x * 10 + (c & 15);
}
#define ll long long 
#define lll __int128_t
#define pb push_back
#define mp make_pair
typedef pair < int,int> ii;
typedef vector<ii> vii;
typedef vector<ll>vl;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
ll hashPrime = 1610612741;

const int MAX = 1000001; 
struct Query 
{ 
    ll l, r, idx; 
}; 
bool cmp(Query x, Query y) 
{ 
    return x.r < y.r; 
} 

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

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); 
  
        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++; 
        } 
    } 
  
    // print answer for each query 
    for (ll i=0; i<q; i++) 
        cout << ans[i] << endl; 
} 
 
int main() 
{ 
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    ll i, j, k, n, m;
    cin >> n >> m;
    ll a[n + 1];
    for (i = 0; i < n;i++){
        cin >> a[i];
    }
    Query queries[m + 1];
    for (i = 1; i <= m;i++){
        cin >> k >> j;
        queries[i - 1].idx = i - 1;
        queries[i - 1].l = k-1;
        queries[i - 1].r = j-1;
    }
    sort(queries, queries + m, cmp);
    answeringQueries(a, n, queries, m);
    return 0; 
} 

Measured memory_bytes: 35088