#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
#include <cstdio>
#include <string>
#include <cmath>
#include <queue>
#include <tuple>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <random>
#include <set>
#include <stack>
#include <time.h>

//#include <bits/stdc++.h>
#define maxs(x,y) x = max(x,y)
#define mins(x,y) x = min(x,y)
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define repr(i, n) for (int i = (n) - 1; i >= 0; i--)
#define FOR(i,i0,n) for(int (i)=(i0);(i)<(n);(i)++)
#define FORR(i,i0,n) for(int (i)=(n)-1; (i)>=(i0);(i)--)
#define SORT(x) sort(x.begin(),x.end())
#define SORTR(x) sort(x.begin(),x.end(),greater<vector<int>>())
#define rn return
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define mt make_tuple

using namespace std;
using ll = long long;
typedef std::pair<int,int> pii;
typedef std::pair<int,double> pid;
typedef std::vector<int> vi;
typedef std::vector<pii> vii;

#define PI 3.14159265358979323846264338327950L
const int mod = 1000000007;




struct item{ // CHANGE
    int val;
};

class SegTree{
public:
    int size;
    vector<item> values;
    
    SegTree(int n){
        size = 1;
        while(size<n) size*=2;
        values.resize(size*2-1);
    }
    
    item NEUTRAL_ELEMENT = {0}; // CHANGE
    item single(int val) { // CHANGE
        return {val};
    }
    item merge(item a, item b){ // CHANGE
        return {a.val+b.val};
    }
    
    
    void build(vector<int>& a){
        build(a,0,0,size);
    };
    void build(vector<int>& a, int node, int nodeL, int nodeR){
        if (nodeR-nodeL == 1) {
            if(nodeL<a.size()) values[node] = single(a[nodeL]); // SINGLE
            return;
        }
        int m = (nodeL+nodeR)/2;
        build(a,node*2+1,nodeL,m);
        build(a,node*2+2,m,nodeR);
        values[node] = merge(values[node*2+1],values[node*2+2]);
    }
    
    
    
    void set(int index, int val){
        set(index,val,0,0,size);
    }
    void set(int index, int val, int node, int nodeL, int nodeR){
        if (nodeR-nodeL==1) {
            values[node]= single(val); // SINGLE
            return;
        }
        int m = (nodeL+nodeR)/2;
        if (index < m) set(index,val,node*2+1,nodeL,m);
        else set(index,val,node*2+2,m,nodeR);
        values[node] = merge(values[node*2+1],values[node*2+2]);
    }
   
    
    
    void add(int index, int val){
        add(index,val,0,0,size);
    }
    void add(int index, int val, int node, int nodeL, int nodeR){
        if (nodeR-nodeL==1) {
            values[node].val += val; // SINGLE
            return;
        }
        int m = (nodeL+nodeR)/2;
        if (index < m) add(index,val,node*2+1,nodeL,m);
        else add(index,val,node*2+2,m,nodeR);
        values[node] = merge(values[node*2+1],values[node*2+2]);
    }
    
    
    
    item calc(int l, int r){
        return calc(l,r,0,0,size); 
    }
    item calc(int l,int r, int node, int nodeL, int nodeR){
        if (r<=nodeL || l>=nodeR) return NEUTRAL_ELEMENT;
        if (l<=nodeL && nodeR<=r) return values[node];
        int m = (nodeL+nodeR)/2;
        return merge(calc(l,r,node*2+1,nodeL,m),calc(l,r,node*2+2,m,nodeR));
    }

};



void solve(){
    int n,q;
    cin >> n >> q;
    vector<int> a(n);
    rep(i,n) cin >> a[i];
    vector<vector<int>> ps(n);
    int last[1001001];
    memset(last,-1,sizeof last);
    
    for(int i = 0; i < n; i++){
        int l = last[a[i]];
        last[a[i]] = i;
        if (l==-1)continue;
        
        ps[l].emplace_back(i);
    }
    
    vector<vector<pii>> qs(n,vector<pii>());
    rep(i,q){
        int l,r;
        cin >> l >> r;
        l--,r--;
        qs[l].emplace_back(r,i);
    }
    
    SegTree st(n);
    
    vector<int> ans(q);
    for(int x = n-1; x >= 0; x--){
        for(auto e:ps[x]){
            st.add(e,1);
        }
        for(auto e:qs[x]){
            int r = e.first - x + 1 - st.calc(0,e.first+1).val;
            ans[e.second] = r;
        }
    }
    
    for(auto e:ans) cout << e << endl;
    
    
}


int main(){
    int T;
    //cin >> T;
    T = 1;
    while(T--){
        solve();
        cout << endl;
    }
}











Measured memory_bytes: 64136