// This problem is the same as DQUERY: https://www.spoj.com/problems/DQUERY/

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef int Int;
typedef pair<Int, Int> pii;
typedef pair<Int, double> pid;
typedef pair<double, double> pdd;
typedef pair<Int, pii> pip;
typedef pair<pii, Int> ppi;
typedef pair<double, Int> pdp;
typedef vector<Int> veci;
typedef vector<double> vecd;
typedef vector<int> veci;
typedef vector<ll> vecll;
typedef vector<double> vecd;
typedef vector<pii> vecpii;
typedef vector<ppi> vecppi;
typedef vector<veci> mati;
typedef vector<vecll> matll;
typedef vector<vecd> matd;
#define PB(x) push_back(x)
#define EB(x) emplace_back(x)
#define ALL(x) x.begin(),x.end()
#define SZ(x) (x).size()
#define CLR(x) memset(x,0,sizeof x)
#define pdebug() printf("%d\n",__LINE__)
#define REP(i, a, b) for(int i = (a);i <= (b);i++)
#define FORO(i, n) REP(i,0,(int)n-1)
#define FORI(i, n) REP(i,1,(int)n)
#define FORIT(i, t) for(auto i = t.begin();i != t.end();i++)
#define eps 1e-6
#define sqr(x) ((x)*(x))
#define dist(_a, _b) sqrt(sqr(_a.A-_b.A)+sqr(_a.B-_b.B))
#define norm(_a) sqrt(sqr(_a.A)+sqr(_a.B))
#define DEBUG 1
#if DEBUG
#define DUMP(a) do { std::cout << #a " = " << (a) << ", "; } while(false)
#define DUMPLN(a) do { std::cout << #a " = " << (a) << std::endl; } while(false)
#else
#define DUMP(a)
#define DUMPLN(a)
#endif
template<typename T, typename U>
inline void getMin(T &a, U b) { if (a > b) a = b; }
template<typename T, typename U>
inline void getMax(T &a, U b) { if (a < b) a = b; }
template<typename T>
vector<T> getVector(const int n) { return vector<T>(n); }
template<typename T>
vector<T> getVector(const int n, const T a) { return vector<T>(n, a); }
template<typename T>
vector<T> getEmptyVector() { return vector<T>(); }
template<typename T>
void appendAll(vector<T> &a, vector<T> b) { a.insert(a.end(), b.begin(), b.end()); }
template<class T1, class T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
#define X first
#define Y second
const int dx[4] = {1, -1, 0, 0};
const int dy[4] = {0, 0, 1, -1};
const ll MOD = 1000000007;
const int inf = 1 << 27;
const ll llinf = 1LL << 50;
const int NIL = -inf;
int popcount(int x) { return __builtin_popcount(x); }

const int MAXN = 1<<20;
const int MAXLOGN = 20;

int pos[MAXN];

int tree[MAXN];
struct NODE {
  int v;
  int L, R;
} dat[2 * MAXN * MAXLOGN];

int ndat;

int build(int l, int r) {
    int idx = ndat++;
    if (r - l == 1) {
        dat[idx].v = 0;
        dat[idx].L = dat[idx].R = -1;
    } else {
        dat[idx].v = 0;
        dat[idx].L = build(l, (r + l) / 2);
        dat[idx].R = build((r + l) / 2, r);
    }
    return idx;
}

int update(int ix, int l, int r, int k, int v) {
    if (k == -1) return -1;
    int idx = ndat++;
    int mid = (l + r) / 2;
    if (ix < mid) {
        dat[idx].L = update(ix, l, (l + r) / 2, dat[k].L, v);
        dat[idx].R = dat[k].R;
    } else {
        dat[idx].L = dat[k].L;
        dat[idx].R = update(ix, (l + r) / 2, r, dat[k].R, v);
    }
    dat[idx].v = dat[k].v + v;
    return idx;
}

int query(int lo, int l, int r, int id) {
    if (r <= lo) return 0;
    if (lo <= l) {
        return dat[id].v;
    } else {
        return query(lo, l, (l + r) / 2, dat[id].L) + query(lo, (l + r) / 2, r, dat[id].R);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int N, Q;
    cin >> N >> Q;

    tree[0] = build(1, N + 1);

    for (int i = 1; i <= N; i++) {
        int x;
        cin >> x;
        int posx = pos[x];
        if (posx != 0) {
            tree[i] = update(i, 1, N + 1, update(posx, 1, N + 1, tree[i - 1], -1), 1);
        } else {
            tree[i] = update(i, 1, N + 1, tree[i - 1], 1);
        }
        pos[x] = i;
    }

    for (int qq = 0; qq < Q; qq++) {
        int l, r;
        cin >> l >> r;
        cout << query(l, 1, N + 1, tree[r]) << endl;
    }

    return 0;
}

Measured memory_bytes: 251452