#include <iostream>
#include <tuple>
#include <algorithm>
using namespace std;
const int MAXN = 100001;
const int MAXQ = 1000001;
pair<int, int>S[MAXN];
int v[MAXN];
int ans[MAXQ];
int xi;
int sj;
struct th{
    int first, second, third;
} a[MAXQ];

bool cmp(th c, th b) {
    if( c.second <= b.second) return true;
    return false;
}
int main() {
    freopen("rmq.in", "r", stdin);
    freopen("rmq.out", "w", stdout);
    int N, Q;
    cin >> N >> Q;
    for(int i = 1; i <= N; i++) {
        cin >> v[i];
    }
    for(int i = 1; i <= Q; i++) {
        cin >> a[i].first >> a[i].second;
        a[i].third = i;
    }
    sort(a + 1, a + Q + 1, cmp);
    int l = 0;
    for(int i = 1; i <= Q; i++) {
        while(l < a[i].second) {
            l++;
            while(S[sj].first > v[l] && sj > 0) sj--;
            sj++;
            S[sj] = {v[l], l};
        }
        /*cout << a[i].first << ' ' << a[i].second << "\n";
        for(int j = 1; j <= sj; j++) cout << S[j].first << ' ';
        cout << '\n';cout << '\n';*/
        int st = 1, dr = sj;
        int best = 0;
        while(st <= dr) {
            int mid = (st + dr) / 2;
            if(S[mid].second < a[i].first) st = mid + 1;
            else {
                dr = mid - 1;
                best = S[mid].first;
            }
        }
        ans[a[i].third] = best;
    }
    for(int i = 1; i <= Q; i++) {
        cout << ans[i] << '\n';
    }
}