#include <cstdio>
#include <vector>
#define NMAX 100023
#define ARBMAX 400023
using namespace std;
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);
    scanf("%d%d",&n,&m);
    int minim=1000000023,pos=0;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&nr);
        val2[i]=nr;
        if(minim>nr)
        {
            minim=nr;
            pos=i;
        }
        update(1,n,1,i,nr);
   // printf("%d\n",arb[query(1,n,2,5,1)].val);
    }
    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++)
    {
        scanf("%d%d",&n1,&n2);
        n1=noduri[n1];
        n2=noduri[n2];
        int lca=0;
        while(1)
        {
           // printf("%d %d\n",n1,n2);
          //  printf("%d %d\n",hp[n1],hp[n2]);
            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("\n");
        printf("%d\n",val[lca]);
    }
}