//IncubatorMan
#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;
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 << ')';
}

void dbg_out() { cerr << endl; }

template<typename Head, typename... Tail>
void dbg_out(Head H, Tail... T) {
    cerr << ' ' << H;
    dbg_out(T...);
}

#ifdef KAMOL
#define dbg(...) cerr << '(' << #__VA_ARGS__ << ')'<<':', dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif
#define ll long long
#define lll __int128_t
#define pb push_back
#define mp make_pair
#define All(x) (x).begin(),(x).end()
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((uint_fast32_t) chrono::steady_clock::now().time_since_epoch().count());
ll hashPrime = 1610612741;

// 1 indexed
class BIT {
private:
    vector<int> Tree;
    int sz;
    int logN;
public:
    int query(int ind) {
        int sum = 0;
        for (int i = ind; i > 0; i -= i & -i) {
            sum += Tree[i];
        }
        return sum;
    }

    BIT(const vector<int> &arr) {
        sz = arr.size();
        logN = (int) log2(sz);
        Tree.resize(sz + 1);
        for (int i = 1; i <= sz; i++) {
            for (int ind = i; ind <= sz; ind += ind & -ind) {
                Tree[ind] += arr[i - 1];
            }
        }

    }
    BIT(int n){
        sz = n+1;
        logN = (int) log2(sz);
        Tree.resize(sz + 1,0);
    }

    void update(int ind, int newValue) {
        for (int i = ind; i <= sz; i += i & -i) {
            Tree[i] += newValue;
        }
    }

    int lower_bound(int v) {
        int pos = 0;
        int sum = 0;
        for (int i = logN; i >= 0; i--) {
            if (pos + (1 << i) <= sz && sum + Tree[pos + (1 << i)] < v) {
                pos += (1 << i);
                sum += Tree[pos];
            }
        }
        pos++;
        return pos;
    }


};
void solve() {
    int n,q;
    cin>>n>>q;
    vi A(n+1);
    vi lastSeen(n+2,n+1);
    for(int i=1;i<=n;i++){
        cin>>A[i];
    }
    vi ans(q);

    vector<vii> X(n+1);

    for(int i=0;i<q;i++){
        int l,r;
        cin>>l>>r;
        X[l].emplace_back(r,i);
    }

    BIT oj = BIT(n+1);

    for(int i=n;i>0;i--){
        int ind = lastSeen[A[i]];
        oj.update(ind,-1);
        oj.update(i,1);
        lastSeen[A[i]]=i;
        for(ii x : X[i]){
            ans[x.second]=oj.query(x.first);
        }

    }
    for(int x : ans){
        cout<<x<<endl;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
#ifdef KAMOL
    freopen("/Users/kamolkumarpaul/Desktop/kamol/contest/CodeForces/ClionProjectContest/in.txt", "r", stdin);
    //freopen("out.txt","w",stdout);
#endif
    int test = 1;
    //cin >> test;
    while (test--) {
        solve();
    }
    return 0;
}

Measured memory_bytes: 33196