#include <bits/stdc++.h>

using namespace std;

const int N = 500000;
const int B = 700;

struct query {
  int l, r, i;
  bool operator<(const query &other) const {
    return make_pair(l / B, r) < make_pair(other.l / B, other.r);
  }
};

int c[N];
query qs[N];
int ans[N];
int f[N], cnt = 0;

void add(int value) {
  if(++f[value] == 1)
    cnt++;
}

void remove(int value) {
  if(--f[value] == 0)
    cnt--;
}

int main() {
  int n, q; scanf("%d %d", &n, &q);
  for(int i = 0; i < n; ++i) {
    scanf("%d", c + i);
  }
  for(int i = 0; i < q; ++i) {
    int l, r; scanf("%d %d", &l, &r);
    qs[i] = {l - 1, r - 1, i};
  }
  sort(qs, qs + q);
  int cur_l = 0, cur_r = -1;
  for(int i = 0; i < q; ++i) {
    while(cur_l > qs[i].l) {
      add(c[--cur_l]);
    }
    while(cur_r < qs[i].r) {
      add(c[++cur_r]);
    }
    while(cur_l < qs[i].l) {
      remove(c[cur_l++]);
    }
    while(cur_r > qs[i].r) {
      remove(c[cur_r--]);
    }
    ans[qs[i].i] = cnt;
  }
  for(int i = 0; i < q; ++i) {
    printf("%d\n", ans[i]);
  }
  return 0;
}
