#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int sz = 5e5+5, rt = 1000;

int a[sz], cnt[sz], ans[sz], now;

struct dtt {
   int l, r, id;
} quers[sz];

bool cmp(dtt a, dtt b) {
   if(a.l / rt == b.l / rt) return a.r < b.r;
   return a.l < b.l;
}

inline void add(int x) {
   if(!cnt[a[x]]) now++;
   cnt[a[x]]++;
}

inline void del(int x) {
   cnt[a[x]]--;
   if(!cnt[a[x]]) now--;
}

int main() {
   int n, q;
   scanf("%d %d", &n, &q);
   for(int i=0; i<n; i++) scanf("%d", &a[i]);
   for(int i=0; i<q; i++) {
      int x, y;
      scanf("%d %d", &x, &y);
      quers[i] = {x-1, y-1, i};
   }
   sort(quers, quers+q, cmp);

   for(int i=0, l=0, r=-1; i<q; i++) {
      while(l < quers[i].l) del(l++);
      while(quers[i].l < l) add(--l);
      while(r < quers[i].r) add(++r);
      while(quers[i].r < r) del(r--);
      ans[quers[i].id] = now;
   }
   for(int i=0; i<q; i++) printf("%d\n", ans[i]);
}
