#include <bits/stdc++.h>
#define FAST_INPUT ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
 
using namespace std;
 
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
 
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif
 
using ll= long long;
const int mxN = 500;
const ll INF = 0x3f3f3f3f3f3f3f3fL;
// ll dist[mxN][mxN];
 
void dfs(ll u, vector<vector<ll>>& graph, vector<bool>& visited){
    if(visited[u])
        return;
    visited[u] = true;
    for(ll v: graph[u]){
        dfs(v, graph, visited);
    }
}

bool relax(vector<ll>& dist, vector<vector<ll>>& edges, vector<bool>& visited){
    bool changed = false;
    for(vector<ll>& edge: edges){
        ll u = edge[0];
        ll v = edge[1];
        ll w = edge[2];

        if(visited[u] && visited[v] && dist[u] != INF){
            if(dist[v] > dist[u] + w){
                dist[v] = dist[u] + w;
                // if(v ==  visited.size() - 1)
                    changed = true;
                // cout << u + 1 << " " << v + 1<< " " << dist[u] << " " << dist[v] << endl;
            }
        }
    }
    return changed;
}

void dijkstra(ll s, vector<ll>& dist, vector<vector<pair<ll,ll>>>& graph){
    priority_queue<pair<ll, int>, vector<pair<ll,int>>, greater<pair<ll,int>>> pq;
    pq.push({0,s});
    dist[s] = 0;
    while(!pq.empty()){
        pair<ll,int> top = pq.top(); pq.pop();
        ll u = top.second;
        ll d = top.first;
        if(d > dist[u])
            continue;

        for(pair<ll,ll>& next: graph[u]){
            ll v = next.first;
            ll w = next.second;
            if(dist[v] > d + w){
                dist[v] = d + w;
                pq.push({dist[v], v});
            }            
        }
    }
}

const int N = 1e6 + 1;


bool good(vector<int>& nums, int mid, int k){
    int count = 0;

    for(int i = 0; i < nums.size(); i++){
        int n = nums[i];
        count += (n / mid + (n%mid != 0) - 1);
    }

    return count <= k;
}

// const int N = 1e6 + 1;

// void solve() {
//     // int k; cin >> k;

//     // for(int i =1 ; i <= 100; i++){
//     //     ll st = 7;
//     //     for(int j = 0; j < 10; j++){
//     //         if(st >= i && st % i == 0){
//     //             cout << i << " " << st << " " << j + 1 << " " << st/i << endl;
//     //             break;
//     //         }
//     //         st *= 10;
//     //         st += 7;
//     //     }
//     //     cout << i << " " << -1 << endl;
//     // }

//     // vector<int> digits;
//     // while(k){
//     //     digits.push_back(k % 10);
//     //     k/=10;
//     // }
//     // reverse(digits.begin(), digits.end());

//     // vector<int> ans;
//     // for(int i = 0; i <= N; i++){
//     //     for(int d = 0; d <= 9; d++){
//     //         for(int j = i; j >= 0; j--){

//     //         }
//     //     }
//     // }

//     // while(k){
//     //     int digit = k % 10;
//     //     k/=10;

//     // }

    
// }

const int MAX = 1000000;
  
int block;
  
struct Query {
    int L, R, index, result;
};
  
bool compare(Query x, Query y) {
    if (x.L / block != y.L / block)
        return x.L / block < y.L / block;
  
    return x.R < y.R;
}
  
bool compare1(Query x, Query y) {
    return x.index < y.index;
}
  
void queryResults(int a[], int n, Query q[], int m) {
    block = (int)sqrt(n);
  
    sort(q, q + m, compare);
  
    int currL = 0, currR = 0;
    int curr_Diff_elements = 0;
  
    int freq[MAX] = { 0 };
  
    for (int i = 0; i < m; i++) {
          
        int L = q[i].L, R = q[i].R;
  
        while (currL < L) {
              
            freq[a[currL]]--;
            if (freq[a[currL]] == 0)
                curr_Diff_elements--;
              
            currL++;
        }
  
        while (currL > L) {
            freq[a[currL - 1]]++;
  
            if (freq[a[currL - 1]] == 1)
                curr_Diff_elements++;
              
            currL--;
        }
        while (currR <= R) {
            freq[a[currR]]++;
  
            if (freq[a[currR]] == 1)
                curr_Diff_elements++;
              
            currR++;
        }
  
        while (currR > R + 1) {
  
            freq[a[currR - 1]]--;
  
            if (freq[a[currR - 1]] == 0)
                curr_Diff_elements--;
              
            currR--;
        }
        q[i].result = curr_Diff_elements;
    }
}
  
void printResults(Query q[], int m) {
    sort(q, q + m, compare1);
    for (int i = 0; i < m; i++) {
        cout << q[i].result << endl;
    }
}

void solve() {
    int n, q;
    cin >> n >> q;
    int colors[n];
    Query queries[q];
    for (int i=0; i<n; i++) {
        cin >> colors[i];
    }
    
    for (int i=0; i<q; i++) {
        int l, r;
        cin >> l >> r;
        l--; r--;
        Query &query=queries[i];
        query.L=l;
        query.R=r;
        query.index=i;
    }
    
    queryResults(colors, n, queries, q);
    printResults(queries, q);
}
 
int main() {
    FAST_INPUT;
    
    solve();
    return 0;
}

Measured memory_bytes: 17416