#include <cstdio>
#include <iostream>
using namespace std;
const int maxn = 500000 + 5;
const int maxm = maxn * 40;
int n, T, a[maxn], rt[maxn];
int L[maxm], R[maxm], sum[maxm], tot = 0;
int la[maxn + maxn + 1];
int build(int l, int r) {
    int pos = ++tot;
    sum[pos] = L[pos] = R[pos] = 0;
    if (l < r) {
        int mid = (l + r) >> 1;
        L[pos] = build(l, mid);
        R[pos] = build(mid + 1, r);
    }
    return pos;
}
int update(int pre, int idx, int v, int l, int r) {
    int pos = ++tot;
    L[pos] = L[pre];
    R[pos] = R[pre];
    sum[pos] = sum[pre] + v;
    if (l < r) {
        int mid = (l + r) >> 1;
        if (idx <= mid)
            L[pos] = update(L[pre], idx, v, l, mid);
        else
            R[pos] = update(R[pre], idx, v, mid + 1, r);
    }
    return pos;
}
int query(int idx, int pre, int l, int r) {
    if (l == r)
        return sum[pre];
    int mid = (l + r) >> 1;
    if (idx <= mid)
        return query(idx, L[pre], l, mid) + sum[R[pre]];
    else
        return query(idx, R[pre], mid + 1, r);
}
int main(void) {
    scanf("%d%d", &n, &T);
    for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
    memset(la, -1, sizeof(la));
    rt[0] = build(1, n);
    for (int i = 1; i <= n; ++i) {
        int v = a[i];
        if (la[v] == -1) {
            rt[i] = update(rt[i - 1], i, 1, 1, n);
        } else {
            int t = update(rt[i - 1], la[v], -1, 1, n);
            rt[i] = update(t, i, 1, 1, n);
        }
        la[v] = i;
    }
    while (T--) {
        int x, y;
        scanf("%d%d", &x, &y);
        cout << query(x, rt[y], 1, n) << endl;
    }
    return 0;
}

/sandbox/1/a.cpp: In function 'int main()':
/sandbox/1/a.cpp:37:2: error: 'memset' was not declared in this scope
   37 |  memset(la, -1, sizeof(la));
      |  ^~~~~~
/sandbox/1/a.cpp:3:1: note: 'memset' is defined in header '<cstring>'; did you forget to '#include <cstring>'?
    2 | #include<iostream>
  +++ |+#include <cstring>
    3 | using namespace std;
/sandbox/1/a.cpp:35:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |  scanf("%d%d", &n, &T);
      |  ~~~~~^~~~~~~~~~~~~~~~
/sandbox/1/a.cpp:36:36: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |  for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
      |                               ~~~~~^~~~~~~~~~~~~
/sandbox/1/a.cpp:51:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |   int x, y; scanf("%d%d", &x, &y);
      |             ~~~~~^~~~~~~~~~~~~~~~