#include <iostream>
#include <queue>
#include <fstream>
#include <algorithm>

using namespace std;
ifstream fin("rmq.in");
ofstream fout("rmq.out");
typedef pair<int, int> pll;
#define X first
#define Y second
#define r(_x) const _x&
struct cmp{
    bool operator()(r(pll) a, r(pll) b)
{
    return a.X < b.X;
}
};

const int Nmax = 100000;
pll arb[Nmax * 4 + 10];
int n;
vector<pll> v, v2;
void buildarb(vector<pll> &p1 = v, vector<pll> &p2 = v2, int i=1)
{
    pll t = p1[0];
    p1.erase(p1.begin());
    arb[i]=t;
    p2.clear();
    for(int i=0; i<p1.size(); i++)
    {
        if(p1[i].Y > t.Y)
        {
            p2.push_back(p1[i]);
            p1.erase(p1.begin() + i);
            i--;
        }
    }
    for(int i=0; i<p2.size()/2; i++)
    {
        swap((int &)(&p2[i]), (int &)(&p2[p2.size()-i-1]));
    }
    if(!p1.empty())
        buildarb(p1, p2, i*2);
    if(!p2.empty())
        buildarb(p2, p1, i*2 + 1);
}
int m(int a, int b, int i=1)
{
    int y = arb[i].Y;
    if(a <= y && y <= b)
        return arb[i].X;
    if(y < a)
        return m(a, b, 2*i + 1);
    else
        return m(a, b, 2*i);
    return -1;
}

int main()
{
    int q;
    fin >> n >> q;
    for(int i=0; i<n; i++)
    {
        int x ;
        fin >> x;
        v[i]={x, i};
    }
    sort(v.begin(), v.end(), cmp);
    buildarb();
    for(int i=0; i<q; i++)
    {
        int a, b;
        fin >> a >> b;
        fout << m(a-1, b-1) << "\n";
    }
    return 0;
}