#include <iostream>
#include <iomanip>
#include <fstream>
#include <cstdio>
#include <sstream>
#include <cassert>
#include <vector>
#include <string>
#include <bitset>
#include <cmath>
#include <algorithm>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <random>
#include <chrono>
#include <ctime>

using namespace std;

#define en '\n'
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) int((x).size())

typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair <ll, ll> pll;

const int INF = 1e9 + 7;
const ll INFLL = 1e18;
const double EPS = 1e-9;
const double PI = 3.1415926535897932384626433832795;
const int MAX_SIZE = 5e5;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

bool IS_ONE_TEST = 1;
ld START_TIME, TIME;

void fast_in_out() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

struct Fenwick {
    int n;
    vector<ll> f;

    Fenwick(int _n) {
        n = _n;
        f.assign(n, 0);
    }

    void update(int i, ll v) {
        for (; i <= n; i += i & -i) {
            f[i] += v;
        }
    }

    ll get_sum(int i) {
        ll s = 0;
        for (; i > 0; i -= i & -i) {
            s += f[i];
        }
        return s;
    }

    ll get(int L, int R) {
        return get_sum(R) - get_sum(L - 1);
    }
};

struct SegmentTree {
    int n, index, qL, qR;
    ll val, res, mx, mn;
    vector<ll> tree;
//    vector<ll> bonus;
    vector<ll> a;

    SegmentTree(int _n) {
        n = _n;
        tree.assign(4 * n, 0);
//        bonus.assign(4 * n, 0);
    }

    void update_vertex(int v, int l, int r) {
        int m = (r + l) / 2, vL = 2 * v, vR = vL + 1;
        tree[v] = tree[vL] + tree[vR];
    }
    void build(vector<ll>& _a) {
        a = _a;
        build_tree(1, 0, n);
    }

    void build_tree(int v, int l, int r) {
        if (l + 1 == r) {
            tree[v] = a[l];
            return;
        }
        int m = (l + r) / 2, vL = v * 2, vR = vL + 1;
        build_tree(vL, l, m);
        build_tree(vR, m, r);
        update_vertex(v, l, r);
    }

    void update_index(int _index, ll _val) {
        index = _index;
        val = _val;
        update_index_tree(1, 0, n);
    }

    void update_index_tree(int v, int l, int r) {
        if (l + 1 == r) {
            tree[v] = val;
            return;
        }
        int m = (l + r) / 2, vL = v * 2, vR = vL + 1;
        if (index < m) update_index_tree(vL, l, m);
        else update_index_tree(vR, m, r);
        update_vertex(v, l, r);
    }

    /*
    void push(int v, int l, int r) {
        int m = (r + l) / 2, vL = 2 * v, vR = vL + 1;
        tree[v] += bonus[v] * (r - l);
        bonus[vL] += bonus[v];
        bonus[vR] += bonus[v];
        bonus[v] = 0;
    }

    void update_segment(int _qL, int _qR, ll _val) {
        qL = _qL;
        qR = _qR + 1;
        val = _val;
        update_segment_tree(1, 0, n);
    }

    void update_segment_tree(int v, int l, int r) {
        if (qL <= l && r <= qR) {
            bonus[v] += val;
            return;
        }
        push(v, l, r);
        int m = (l + r) / 2, vL = v * 2, vR = vL + 1;
        if (qL < m) update_segment_tree(vL, l, m);
        if (m < qR) update_segment_tree(vR, m, r);
        update_vertex(v, l, r);
    }
    //*/

    ll get(int _qL, int _qR) {
        qL = _qL;
        qR = _qR + 1;
        res = 0;
        get_tree(1, 0, n);
        return res;
    }

    void get_tree(int v, int l, int r) {
        if (qL <= l && r <= qR) {
            res += tree[v];
            return;
        }
//        push(v, l, r);
        int m = (l + r) / 2, vL = v * 2, vR = vL + 1;
        if (qL < m) get_tree(vL, l, m);
        if (m < qR) get_tree(vR, m, r);
    }
};


void solve() {
    int n, q;
    cin >> n >> q;
    vector<int> cnt(n + 1, 0), last(n + 1, -1), a(n), ans(q);
    vector<vector<int>> all_q(n);
    vector<pii> qs;
    for (auto &i: a) cin >> i;
    for (int i = 0; i < q; ++i) {
        int l, r;
        cin >> l >> r;
//        --l; --r;
        all_q[r - 1].emplace_back(i);
        qs.emplace_back(l, r);
    }
    Fenwick t(n);
    for (int i = 0; i < n; ++i) {
        if (last[a[i]] != -1) {
            t.update(last[a[i]] + 1, -1);
        }
        last[a[i]] = i;
        t.update(last[a[i]] + 1, 1);
        for (auto &id: all_q[i]) {
            ans[id] = t.get(qs[id].first, qs[id].second);
        }
    }
    for (auto &i: ans) {
        cout << i << en;
    }
}

int main() {
    START_TIME = clock();
    fast_in_out();
    int TESTS = 1;
    if (!IS_ONE_TEST) cin >> TESTS;
    while (TESTS--) { solve(); }
#ifdef __APPLE__
    TIME = (clock() - START_TIME) / CLOCKS_PER_SEC;
    cerr << en << TIME * 1000 << " ms." << en;
#endif
    return 0;
}

/*
     ▄▀▀▀▄
▄███▀░◐░░░▌
    ▌░░░░░▐
    ▐░░░░░▐
    ▌░░░░░▐▄▄
    ▌░░░░▄▀▒▒▀▀▀▀▄
   ▐░░░░▐▒▒▒▒▒▒▒▒▀▀▄
   ▐░░░░▐▄▒▒▒▒▒▒▒▒▒▒▀▄
    ▀▄░░░░▀▄▒▒▒▒▒▒▒▒▒▒▀▄
      ▀▄▄▄▄▄█▄▄▄▄▄▄▄▄▄▄▄▀▄
           ▌▌░▌▌
           ▌▌░▌▌
         ▄▄▌▌▄▌▌        */


Measured memory_bytes: 40172