#include<stdio.h>
#include<set>

using namespace std;

#define SIZE 131072

int n, m;

set<int> s[2*SIZE - 1];

int c[2*SIZE - 1];
int g[2*SIZE - 1];
int d[2*SIZE - 1];

FILE *f, *fo;

int i, j;
int p, q;

set<int> *ps[20];
int lps;

int def(int dv, int gv, int c)
{
 g[c] = gv;
 d[c] = dv;
 
 if(gv > dv)
 {
  def(dv, dv + (gv - dv)/2, 2*c + 1);
  def(dv + (gv - dv)/2 + 1, gv, 2*c + 2);
 }
}

void braz(int p, int k, int c)
{
 if(p == d[c] && k == g[c])
 {
  ps[lps++] = &s[c];
  return;
 }
 
 if(p <= g[c*2 + 1])
  braz(p, min(g[c*2 + 1], k), c*2 + 1);
 
 if(k >= d[c*2 + 2])
  braz(max(p, d[c*2 + 2]), k, c*2 + 2);
 
}

set<int> poms;

int res;

int main()
{
 def(0, SIZE - 1, 0);
    
 f = fopen("knjige.in", "r");
 fo = fopen("knjige.out", "w");
 
 fscanf(f, "%d%d", &n, &m);
 
 for(i = 0; i < n; i++)
 {
  fscanf(f, "%d", &p);
  s[SIZE + i - 1].insert(p);
 }
 
 
 for(i = SIZE - 2; i >= 0; i--)
 {
  for(set<int>::iterator it = s[2*i + 1].begin(); it != s[2*i + 1].end(); it++)
   s[i].insert(*it);

  for(set<int>::iterator it = s[2*i + 2].begin(); it != s[2*i + 2].end(); it++)
   s[i].insert(*it);
 }
 
 for(i = 0; i < m; i++)
 {
  fscanf(f, "%d%d", &p, &q);
  
  p--;
  q--;
  
  lps = 0;
  braz(p, q, 0);
  
  p = 0;
  
  for(j = 1; j < lps; j++)
   if(ps[j]->size() > ps[p]->size())
    p = j;
 
  res = ps[p]->size();
  
  poms.clear();
  
  for(j = 0; j < lps; j++)
   if(j != p)
    for(set<int>::iterator it = ps[j]->begin(); it != ps[j]->end(); it++)
     if(ps[p]->find(*it) == ps[p]->end() && poms.find(*it) == poms.end())
     {
      res++;
      poms.insert(*it);
     }
  
  fprintf(fo, "%d\n", res);
 }
 
 return 0;
}
