#include <bits/stdc++.h>
#define MAXN 100002
#define MAXM 1000002

std::vector<int> input(MAXN);
std::vector< std::pair<int, int> > queries;
std::vector<int> parent(MAXN, -1);
std::vector<int> previous(MAXM);
std::vector<int> head(MAXN, -1);
std::vector<int> output(MAXM);
std::stack<int> st;

//std::ios::sync_with_stdio(0), std::cin.tie(0);
std::ifstream fin("rmq.in");
std::ofstream fout("rmq.out");


int find_root(int value) {
    if (parent[value] == -1)
        return value;

    parent[value] = find_root(parent[value]);
    return parent[value];
}


int main() {
    int n, m;
    fin >> n >> m;


    for (int i = 0; i < n; i++) {
        fin >> input[i];
    }

    int l, r;
    for (int i = 0; i < m; i++) {
        fin >> l >> r;
        l--; r--;
        queries.push_back(std::make_pair(l, r));
    }


    for (int i = 0; i < m; i++) {
        previous[i] = head[queries[i].second];
        head[queries[i].second] = i;
    }

    for (int i = 0; i < n; i++) {
        while (!st.empty() && input[st.top()] > input[i]) {
            parent[st.top()] = i;
            st.pop();
        }
        st.push(i);

        for (int query = head[i]; query >= 0; query = previous[query]) {
            output[query] = input[find_root(queries[query].first)];
        }
    }

    for (int i = 0; i < m; i++)
        fout << output[i] << "\n";

    return 0;
}