#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;

struct query {
  int L, R, id;
} q[500020];

const int BLOCK = 1000;

bool cmp(query a, query b) {
  if (a.L / BLOCK != b.L / BLOCK)
    return a.L / BLOCK < b.L / BLOCK;
  else
    return a.R < b.R;
}

int a[500020], cnt[500020], ans[500020];

int main() {
  int n, m;
  scanf("%d", &n);
  scanf("%d", &m);
  for (int i = 1; i <= n; i++)
    scanf("%d", &a[i]);
  for (int i = 0; i < m; i++) {
    scanf("%d%d", &q[i].L, &q[i].R);
    q[i].id = i;
  }
  sort(q, q + m, cmp);
  int L = 0, R = 0, cur = 0;
  for (int i = 0; i < m; i++) {
    int left = q[i].L, right = q[i].R, id = q[i].id;
    while (L < left) {
      cur -= --cnt[a[L++]] == 0;
    }
    while (L > left) {
      cur += ++cnt[a[--L]] == 1;
    }
    while (R < right) {
      cur += ++cnt[a[++R]] == 1;
    }
    while (R > right) {
      cur -= --cnt[a[R--]] == 0;
    }
    ans[id] = cur;
  }
  for (int i = 0; i < m; i++)
    printf("%d\n", ans[i]);
  return 0;
}