#include<iostream>
#include<fstream>
using namespace std;
ifstream f("rmq.in");
ofstream g("rmq.out");
struct element{int x,y;}v[100005];
//in capmul x stocam valoarea
//in campul y stocam indicele
void qSort (element v[100005],int st, int dr){
int maxim,minim,temp,mijl;
maxim=dr;minim=st;
mijl=v[st+(dr-st)/2].x;
do{
        while (v[minim].x<mijl) minim++;
        while (v[maxim].x>mijl) maxim--;
        if(minim<=maxim){
            temp=v[minim].x;
            v[minim].x=v[maxim].x;
            v[maxim].x=temp;
             temp=v[minim].y;
            v[minim++].y=v[maxim].y;
            v[maxim--].y=temp;}
    }while (minim<=maxim);
    if(st<maxim) qSort (v,st,maxim);
    if(minim<dr) qSort (v,minim,dr);}
int main (){
int m,n,i,j,x,y;
f>>n>>m;
for(i=1;i<=n;i++)
    {f>>v[i].x;v[i].y=i;}
// citirea si memorarea valorilor in campuri
qSort(v,1,n);
// sortam crescator ambele campuri in functie x
for(i=1;i<=m;i++)   //pentru fiecare interval
{f>>x>>y;           //ii citim capetele
    j=1;            //parcurgem vectorul sortat
    while (v[j].y<x||v[j].y>y) j++; //pana cand ajungem la primul element cu indicele din y
                                    //in interval, care este implicit cel mic deci solutia
    g<<v[j].x<<"\n";}
return 0;}