#include <cstdio>
#include <vector>
#define NMAX 100023
#define ARBMAX 400023
#define DIM 10000
using namespace std;
char buff[DIM];
int poz=0;
void citeste(int &numar)
{
     numar=0;
     while (buff[poz] < '0' || buff[poz] > '9')
          if (++poz == DIM)
               fread(buff,1,DIM,stdin),poz=0;
     while ('0'<=buff[poz] && buff[poz]<='9')
     {
          numar = numar*10 + buff[poz] - '0';
          if (++poz == DIM)
               fread(buff,1,DIM,stdin),poz=0;
     }
}
int a[NMAX],noduri[NMAX],nodlib=1,hp[NMAX],upmost[NMAX],niv[NMAX],niv_hp[NMAX],t[NMAX],heavy[NMAX],transhp[NMAX],val2[NMAX],val[NMAX];
struct str
{
    int val;
    int pos;
}arb[ARBMAX];
vector<int>adj[NMAX];
int n,m,nr;
int min(int a,int b)
{
    if(a<b) return a;
    return b;
}
void update(int s,int e,int nod,int pos,int num)
{
    if(s==e)
    {
        arb[nod].val=num;
        arb[nod].pos=pos;
    }
    else
    {
        int mij=(s+e)/2;
        if(pos<=mij) update(s,mij,2*nod,pos,num);
        else update(mij+1,e,2*nod+1,pos,num);
        if(arb[2*nod].val<arb[2*nod+1].val) arb[nod]=arb[2*nod];
        else arb[nod]=arb[2*nod+1];
    }
}
int query(int s,int e,int p1,int p2,int nod)
{
    if(s==p1&&e==p2) return nod;
    else
    {
        int mij=(s+e)/2;
        if(p2<=mij) return query(s,mij,p1,p2,2*nod);
        else if(p1>mij) return query(mij+1,e,p1,p2,2*nod+1);
        else
        {
            int px=query(s,mij,p1,mij,2*nod);
            int py=query(mij+1,e,mij+1,p2,2*nod+1);
            if(arb[px].val<arb[py].val) return px;
            else return py;
        }
    }
    return 0;
}
void create(int s,int e,int ta)
{
    if(s>e)
    {
        adj[ta].push_back(0);
        return;
    }
    int nod=query(1,n,s,e,1);
    noduri[arb[nod].pos]=++nodlib;
    adj[ta].push_back(nodlib);
    create(s,arb[nod].pos-1,noduri[arb[nod].pos]);
    create(arb[nod].pos+1,e,noduri[arb[nod].pos]);
}
void makelevels(int nod,int nivel)
{
    niv[nod]=nivel;
    if(adj[nod].empty()) return;
    t[adj[nod][0]]=nod;
    t[adj[nod][1]]=nod;
    vector<int>::iterator it;
    for(it=adj[nod].begin();it!=adj[nod].end();++it)
    {
        makelevels(*it,nivel+1);
    }
}
void make_heavy_path(int nod)
{
    heavy[nod]++;
    if(adj[nod][0]==0&&adj[nod][1]==0)
    {
        hp[nod]=++nodlib;
        niv_hp[nodlib]=niv[nod];
        transhp[nodlib]=nod;
    }
    else
    {
        vector<int>::iterator it;
        for(it=adj[nod].begin();it!=adj[nod].end();++it)
        {
            if(*it!=0) make_heavy_path(*it);
        }
        if(heavy[adj[nod][0]]>heavy[adj[nod][1]]) hp[nod]=hp[adj[nod][0]];
        else hp[nod]=hp[adj[nod][1]];
        niv_hp[hp[nod]]=niv[nod];
        transhp[hp[nod]]=nod;
    }
    heavy[t[nod]]+=heavy[nod];
}
int main()
{
    freopen ("rmq.in","r",stdin);
    freopen ("rmq.out","w",stdout);
    citeste(n),citeste(m);
    int minim=1000000023,pos=0;
    for(int i=1;i<=n;i++)
    {
        citeste(val2[i]);
        if(minim>val2[i])
        {
            minim=val2[i];
            pos=i;
        }
        update(1,n,1,i,val2[i]);
    }
    noduri[pos]=1;
    create(1,pos-1,1);
    create(pos+1,n,1);
    makelevels(1,1);
    nodlib=0;
    make_heavy_path(1);
    for(int i=1;i<=n;i++) val[noduri[i]]=val2[i];
    for(int i=1;i<=nodlib;i++)
    {
        transhp[i]=t[transhp[i]];
    }
    int n1,n2;
    niv[0]=0;
    t[0]=0;
    for(int i=1;i<=m;i++)
    {
        citeste(n1),citeste(n2);
        n1=noduri[n1];
        n2=noduri[n2];
        int lca=0;
        while(1)
        {
            if(hp[n1]==hp[n2])
            {
                if(niv[n1]<niv[n2]) lca=n1;
                else lca=n2;
                break;
            }
            else
            {
                if(niv[transhp[hp[n1]]]>niv[transhp[hp[n2]]]) n1=transhp[hp[n1]];
                else n2=transhp[hp[n2]];
            }
        }
        printf("%d\n",val[lca]);
    }
}