#include<iostream>
#include<fstream>
#include<vector>

using namespace std;
ifstream in("rmq.in");
ofstream out("rmq.out");


const int mx = 130000;
struct element {
    int value;
    int index;
};

bool operator<(const element &a, const element &b) {
    if (a.value < b.value) {
        return true;
    } else if (a.value == b.value) {
        return a.index < b.index;
    }
    return false;
}

bool operator>(const element &a, const element &b) {
    if (a.value > b.value) {
        return true;
    } else if (a.value == b.value) {
        return a.index > b.index;
    }
    return false;
}

bool operator==(const element &a, const element &b) {
    return a.value == b.value && a.index == b.index;
}

int n, q, ln[mx], rn[mx], ft[mx], level[mx], label[mx], label_index[mx], root;
element v[mx];
vector<int> g[mx];

void read() {
    in >> n >> q;
    for (int i = 1; i <= n; i++) {
        in >> v[i].value;
        v[i].index = i;
    }
}

void build_tree() {
    vector<int> st;
    for (int i = 1; i <= n; i++) {
        while (!st.empty() && v[st.back()] > v[i]) {
            st.pop_back();
        }
        if (st.empty()) {
            ln[i] = 0;
        } else {
            ln[i] = st.back();
        }
        st.push_back(i);
    }
    st.clear();

    for (int i = n; i >= 1; i--) {
        while (!st.empty() && v[st.back()] > v[i]) {
            st.pop_back();
        }
        if (st.empty()) {
            rn[i] = 0;
        } else {
            rn[i] = st.back();
        }
        st.push_back(i);
    }
    for (int i = 1; i <= n; i++) {
        if (v[ln[i]] > v[rn[i]]) {
            ft[i] = ln[i];
        } else {
            ft[i] = rn[i];
        }
        g[ft[i]].push_back(i);
        if (ft[i] == 0) {
            root = i;
        }
    }
}


void dfs(int node) {
    if (!g[node].empty()) {
        level[g[node][0]] = level[node] + 1;
        label[g[node][0]] = label[node] * 2;
        label_index[label[g[node][0]]] = g[node][0];
        dfs(g[node][0]);
    }
    if (g[node].size() == 2) {
        level[g[node][1]] = level[node] + 1;
        label[g[node][1]] = label[node] * 2 + 1;
        label_index[label[g[node][1]]] = g[node][1];
        dfs(g[node][1]);
    }
}

int log2(int num) {
    return 31 - __builtin_clz(num);
}

int lca(int a, int b) {
    if (level[b] > level[a]) {
        swap(a, b);
    }
    int a_label = label[a] >> (level[a] - level[b]), b_label = label[b];
    if (a_label == b_label) {
        return label_index[a_label];
    }

    int x = log2(a_label ^ b_label) + 1;
    int lca_label = a_label >> x;
    return label_index[lca_label];
}

void solve() {
    build_tree();
    label[root] = 1;
    label_index[1] = root;
    level[root] = 1;
    dfs(root);


    int a, b;
    while (q--) {
        in >> a >> b;
        out << v[lca(a, b)].value << endl;
    }

}

int main() {

    read();
    solve();
    return 0;
}