var t:array[..]of record

                             l,r,s:longint;

                            end;

     a,b,c,d,root,h:array[..]of longint;

     n,m,i,x,y,cnt:longint;

 procedure swap(var x,y:longint);

 var t:longint;

 begin

  t:=x; x:=y; y:=t;

 end;

 procedure qsort(l,r:longint);

 var i,j,mid:longint;

 begin

  i:=l; j:=r; mid:=a[(l+r)>>];

  repeat

   while mid>a[i] do inc(i);

   while mid<a[j] do dec(j);

   if i<=j then

   begin

    swap(a[i],a[j]);

    swap(c[i],c[j]);

    inc(i); dec(j);

   end;

  until i>j;

  if l<j then qsort(l,j);

  if i<r then qsort(i,r);

 end;

 procedure update(l,r:longint;var p:longint;x:longint);

 var mid:longint;

 begin

  inc(cnt); t[cnt]:=t[p];

  p:=cnt; inc(t[p].s);

  if l=r then exit;

  mid:=(l+r)>>;

  if x<=mid then update(l,mid,t[p].l,x)

   else update(mid+,r,t[p].r,x);

 end;

 function query(p1,p2,l,r,k:longint):longint;

 var mid,t1,t2:longint;

 begin

  if l=r then exit(l);

  t1:=t[t[p2].l].s-t[t[p1].l].s;

  t2:=t[t[p2].r].s-t[t[p1].r].s;

  mid:=(l+r)>>;

  if t1>=k then exit(query(t[p1].l,t[p2].l,l,mid,k))

   else if t2>=k then exit(query(t[p1].r,t[p2].r,mid+,r,k))

    else exit();

 end;

 begin

  assign(input,'bzoj3524.in'); reset(input);

  assign(output,'bzoj3524.out'); rewrite(output);

  readln(n,m);

  for i:= to n do

  begin

   read(a[i]);

   b[i]:=a[i]; c[i]:=i;

  end;

  qsort(,n);

  d[c[]]:=;

  for i:= to n do

   if a[i]<>a[i-] then d[c[i]]:=d[c[i-]]+

    else d[c[i]]:=d[c[i-]];  //离散化

  for i:= to n do h[d[i]]:=b[i]; //离散化后还原原数

  for i:= to n do

  begin

   root[i]:=root[i-];

   update(,n,root[i],d[i]);

  end;

  for i:= to m do

  begin

   readln(x,y);

   writeln(h[query(root[x-],root[y],,n,(y-x+) div +)]);

  end;

  close(input);

  close(output);

 end.