#include <stdio.h>
#include <algorithm>
#include <vector.h>
#include <set.h>
using namespace std;

#define pb push_back

struct Upit {
   int poc, kr, id;
};

bool cmpUpit(Upit u1, Upit u2) {
   if(u1.poc == u2.poc) return u1.id < u2.id;
   return u1.poc < u2.poc;
}

struct KumT {
   int tree[100050];
   int n;

   void Init(int size) {
      n = size;
      for(int i = 1; i <= n; i++) tree[i] = 0;
   }

   void Add(int id, int d) {
      for(int i = id; i <= n; i += i & -i) tree[i] += d;
   }

   int Sum(int id) {
      if(id > n) id = n;
      int res = 0;
      for(int i = id; i > 0; i-= i & -i) res += tree[i];
      return res;
   }
} kum;

int tr[100050];
int a[100050];
vector<int> pos[100050];
int n, q;
Upit upit[100050];

void Input() {
   FILE *fin = fopen("knjige.in", "r");
   fscanf(fin, "%d%d", &n, &q);

   for(int i = 1; i <= 100000; i++) tr[i] = -1;

   for(int i = 1; i <= n; i++) {
      fscanf(fin, "%d", &a[i]);
      pos[a[i]].pb(i);
      tr[a[i]] = 0;
   }

   for(int i = 0; i < q; i++) {
      fscanf(fin, "%d%d", &upit[i].poc, &upit[i].kr);
      upit[i].id = i;
   }
}

int sol[100050];

void Solve() {
   sort(upit, upit + q, cmpUpit);
   kum.Init(n);
   for(int i = 1; i <= 100000; i++) if(tr[i] == 0) kum.Add(pos[i][0], 1);

   int trpos = 1;
   for(int i = 0; i < q; i++) {
      int poc = upit[i].poc, kr = upit[i].kr, id = upit[i].id;

      while(trpos < poc) {
         kum.Add(trpos, -1);
         if(pos[a[trpos]].size() > tr[a[trpos]]+1) kum.Add(pos[a[trpos]][++tr[a[trpos]]], 1);
         trpos++;
      }

      sol[id] = kum.Sum(kr);
   }
}

void Output() {
   FILE *fout = fopen("knjige.out", "w");
   for(int i = 0; i < q; i++) fprintf(fout, "%d\n", sol[i]);
}

int main() {
   Input();
   Solve();
   Output();
}
