#include <fstream>
#include <cstring>

using namespace std;

constexpr int kMaxN = 100000;
constexpr int kMaxM = 1000000;
constexpr int NIL = -1;

struct Query {
    int lo; 
    int next;
} buf[kMaxM];

int head[kMaxN + 1];
int v[kMaxN + 1];
int parent[kMaxN + 1];
int st[kMaxN + 1], ss;
int queryAnswer[kMaxM];

int getRoot(const int node) {
    return (parent[node] == node) ?
        node : parent[node] = getRoot(parent[node]);
}

void Link(const int x, const int y) {
    parent[x] = y;
}

int main() {
    ifstream cin("rmq.in");
    ofstream cout("rmq.out");
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    
    int N, Q; cin >> N >> Q;
    
    for (int i = 1; i <= N; i += 1) {
        cin >> v[i];
    }
    memset(head + 1, NIL, 4 * N);
    for (int i = 0; i < Q; i += 1) {
        int b, e; cin >> b >> e;
        buf[i].lo = b;
        buf[i].next = head[e];
        head[e] = i;
    }

    for (int i = 1; i <= N; i += 1) {
        parent[i] = i;
    }

    v[0] = NIL;
    st[0] = 0; ss = 1;
    for (int i = 1; i <= N; i += 1) {
        while (v[st[ss - 1]] >= v[i]) {
            Link(st[--ss], i);
        }
        st[ss++] = i;
        for (int j = head[i]; j != NIL; j = buf[j].next) {
            queryAnswer[j] = v[getRoot(buf[j].lo)];
        }
    }
    for (int i = 0; i < Q; i += 1) {
        cout << queryAnswer[i] << '\n';
    }
    return 0;
}