#include <bits/stdc++.h>

using namespace std;

const int N = (int) 5e5 + 55;

int fen[N];

void upd(int x, int y) {
  while (x < N) {
    fen[x] += y;
    x |= (x + 1);
  }
}

int get(int x) {
  int res = 0;
  while (x >= 0) {
    res += fen[x];
    x = (x & (x + 1)) - 1;
  }
  return res;
}

int res[N];
vector<pair<int, int>> vec[N];

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, q;
  cin >> n >> q;
  vector<int> c(n);
  for (int i = 0; i < n; i++) {
    cin >> c[i];
    --c[i];
  }
  for (int i = 0; i < q; i++) {
    int l, r;
    cin >> l >> r;
    --l; --r;
    vec[r].emplace_back(l, i);
  }
  vector<int> last(n, -1);
  for (int i = 0; i < n; i++) {
    if (last[c[i]] != -1) {
      upd(last[c[i]], -1);
    }
    last[c[i]] = i;
    upd(i, 1);
    for (auto u : vec[i]) {
      res[u.second] = get(i) - get(u.first - 1);
    }
  }
  for (int i = 0; i < q; i++) {
    cout << res[i] << '\n';
  }
  return 0;
}

#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 10;

int n, m, siz, num;
int w[N], cnt[N], belong[N];
int now, ans[N];

struct query{
	int l, r, id;
}q[N];

//bool cmp(query a, query b)
//{
//	return (belong[a.l] ^ belong[b.l]) ? belong[a.l] < belong[b.l] : ((belong[a.l] & 1) ? a.r < b.r : a.r > b.r);
//}
bool cmp(query a, query b) {
    return (belong[a.l] ^ belong[b.l]) ? belong[a.l] < belong[b.l] : ((belong[a.l] & 1) ? a.r < b.r : a.r > b.r);
}

void add(int pos)
{
	if(!cnt[w[pos]]) ++now;
	++cnt[w[pos]];
}

void del(int pos)
{
	--cnt[w[pos]];
	if(!cnt[w[pos]]) --now;
}

int main()
{
	scanf("%d%d", &n, &m);
	siz = sqrt(n);
	num = ceil((double) n / siz);
//	cout << num << endl;
	for (int i = 1; i <= num; i ++)
	{
		for (int j = (i - 1) * siz + 1; j <= i * siz; j ++)
		{
			belong[j] = i;
		}
	}
	for (int i = 1; i <= n; i ++) scanf("%d", &w[i]);
	for (int i = 1; i <= m; i ++)
	{
		q[i].id = i;
		scanf("%d%d", &q[i].l, &q[i].r);
	}
	sort(q + 1, q + m + 1, cmp);
	int l = 1, r = 0;
	for (int i = 1; i <= m; i ++)
	{
		int ql = q[i].l, qr = q[i].r;
		while(l < ql) del(l ++);
		while(l > ql) add(-- l);
		while(r < qr) add(++ r);
		while(r > qr) del(r --);
		ans[q[i].id] = now;
	}
	for (int i = 1; i <= m; i ++)
		printf("%d\n", ans[i]);
}