#include <cstdio>

#define NMAX 100002
#define NMAX2 198602
#define log2 21

using namespace std;
int n, m, v[NMAX], x, y, fiuS[NMAX], tata[NMAX], fiuD[NMAX], euler[NMAX2], root,  indic;
int first[NMAX], rmq[log2][NMAX2], tmp1, tmp2;
char depth[NMAX];

void make_node(const int &key)
{
    if(key == 1)
    {
        root = key;
        tata[key] = -1;
        return ;
    }
    if(v[key] >= v[key-1])
    {
        fiuD[key-1] = key;
        tata[key] = key-1;
        return ;
    }
    int it = key-1;
    while(tata[it] != -1 && v[tata[it]] > v[key]) it = tata[it];
    tata[key] = tata[it];
    fiuS[key] = it;
    fiuD[tata[it]] = key;
    tata[it] = key;
    if(tata[key] == -1) root = key;
}
void dfs(const int &nod, const int &lvl)
{
    depth[nod] = lvl;
    euler[++indic] = nod;
    first[nod] = indic;
    if(fiuS[nod])
    {
        dfs(fiuS[nod], lvl+1);
        euler[++indic] = nod;
    }
    if(fiuD[nod])
    {
        dfs(fiuD[nod], lvl+1);
        euler[++indic] = nod;
    }
}
void build_rmq()
{
    for(int i = 1; i<= indic; ++i) rmq[0][i] = euler[i];
    for(int i = 1; (1<<i) <= indic; ++i)
    {
        for(int j = 1; j <= indic; ++j)
        {
            if(j + (1<<i)-1 > indic) break;
            rmq[i][j] = (depth[rmq[i-1][j]] < depth[rmq[i-1][j + (1<<(i-1))]]) ? rmq[i-1][j] : rmq[i-1][j + (1<<(i-1))];
        }
    }

}
int query(const int &st, const int &dr)
{
    int pas = 0;
    for(; (1<<pas) <= dr -st +1; ++pas);
    --pas;
    return (depth[rmq[pas][st]] < depth[rmq[pas][dr - (1<<pas) + 1]]) ? rmq[pas][st] : rmq[pas][dr - (1<<pas) + 1];
}

int main()
{
    freopen("rmq.in", "r", stdin);
    freopen("rmq.out", "w", stdout);
    scanf("%d %d", &n, &m);
    for(int i = 1; i<= n; ++i)
    {
        scanf("%d", &v[i]);
        make_node(i);
    }
    dfs(root, 1);
    build_rmq();
    //for(int i = 1; i<= n; ++i) if(depth[i] > 250) while(1){};
    for(; m; --m)
    {
        scanf("%d %d", &x, &y);
        tmp1 = first[x];
        tmp2 = first[y];
        if(tmp1 < tmp2) printf("%d\n", v[query(tmp1, tmp2)]);
        else printf("%d\n", v[query(tmp2, tmp1)]);
    }
    return 0;
}