#include <fstream>
#include <vector>
using namespace std;

namespace{

class ipfstream{
    static constexpr int N = 10000;
    ifstream f;
    char *buf = new char[N], *p = buf, *ep = buf + N;
    void adv(){
        if(++p == ep)
            f.read(p=buf, N); }
public:
    ipfstream(string str): f(str){
        f.read(p, N); }
    ~ipfstream(){
        delete[] buf; }
    ipfstream& operator>>(int& x){
        x = 0;
        for( ; *p < '0'; adv());
        for( ; *p >= '0'; adv()) x = 10 * x + *p - '0';
        return *this; } } f("rmq.in");

class opfstream{
    static constexpr int N = 10000;
    ofstream g;
    char *buf = new char[N], *p = buf, *ep = buf + N;
    void push(char ch){
        *p++ = ch;
        if(p == ep)
            g.write(p=buf, N); }
public:
    opfstream(string str): g(str){}
    ~opfstream(){
        g.write(buf, p-buf);
        delete[] buf; }
    opfstream& operator<<(char ch){
        push(ch);
        return *this; }
    opfstream& operator<<(int x){
        if(x == 0) push('0');
        else{
            int y;
            static constexpr int maxsz = 10;
            char bbuf[maxsz], *pp = bbuf + maxsz - 1, *epp = bbuf + maxsz; 

            while(true){
                *pp-- = '0' + x - 10 * (y = x/10);
                if(!y) break;
                *pp-- = '0' + y - 10 * (x = y/10);
                if(x) continue;
                break; }

            ++pp;
            do{
                push(*pp++);
            } while(pp < epp); }
        return *this; } } g("rmq.out");

constexpr int maxn = 1e5 + 10, maxm = 1e6 + 10;

int v[maxn];
pair<int, int> st[maxn];
vector<pair<int, int>> _left[maxn] = {};

int ret[maxm];

int tt[maxn] = {},rk[maxn] = {}, rhs[maxn] = {};

int find(int x){
    return tt[x] ? tt[x] = find(tt[x]) : x; }

int merge(int x, int y){
    x = find(x), y = find(y);
    if(rk[x] > rk[y]) swap(x, y);
    if(rk[x] == rk[y]) ++rk[y];
    return tt[x] = y; } }
    
int main(){
    int n, m;
    pair<int, int> *p = st + maxn, *ep = p;

    f >> n >> m;
    for(int* vp = v+1, *ep = v+n+1; vp < ep; ++vp) f >> *vp;
    for(int i = 0, x, y; i < m; ++i) f >> x >> y, _left[y].emplace_back(x, i);

    for(int i = 1; i <= n; ++i){
        const int vi = v[i];
        rhs[i] = i;
        while(p < ep && p->second > vi) rhs[merge((p++)->first, i)] = i;
        *--p = make_pair(i, vi);

        for(auto& x : _left[i])
            ret[x.second] = v[rhs[find(x.first)]]; }

    for(int* rp = ret, *ep = ret+m; rp < ep; ++rp) g << *rp << '\n';
    return 0; }