#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e5 + 5, MAXM = 1e6 + 5;
struct query{
    int l, r, idx, ans;
}q[MAXM];
int v[MAXN];
int n, m;
int stiva[MAXM], k;

void solve(){
    cin >> n >> m;
    for(int i = 0; i < n; i++){
        cin >> v[i];
    }
    for(int i = 0; i < m; i++){
        cin >> q[i].l >> q[i].r;
        q[i].l--; q[i].r--;
        q[i].idx = i;
        if(q[i].l > q[i].r)
            swap(q[i].l, q[i].r);
    }

    auto cmp = [](const query& a, const query& b) { return (a.r < b.r); };
    sort(q, q+m, cmp);
    int j = 0;
    for(int i = 0; i < n; i++){
        while(k > 0 && v[stiva[k-1]] >= v[i]){
            k--;
        }
        stiva[k++] = i;

        while(j < m && q[j].r <= i){
            int st = 0, dr = k-1;
            while(st < dr){
                int mj = (st + dr) / 2;

                if(stiva[mj] >= q[j].l){
                    dr = mj;
                }else{
                    st = mj+1;
                }
            }

            q[j].ans = v[stiva[dr]];
            j++;
        }
    }

    auto cmp2 = [](const query& a, const query& b) { return a.idx < b.idx;};
    sort(q, q + m, cmp2);

    for(int i = 0; i < m; i++){
        cout << q[i].ans << '\n';
    }
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    freopen("rmq.in", "r", stdin);
    freopen("rmq.out", "w", stdout);

    solve();

    return 0;
}