#include <bits/stdc++.h>
#define MAXN 100000

std::vector<int> a(MAXN);
std::vector< std::pair<int, int> > queries;
std::vector<int> output;
std::vector<int> parent(MAXN, -1);
std::vector<int> previous(MAXN);
std::vector<int> head(MAXN, -1);


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

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

std::vector<int> rmq(const std::vector<int>& input, const std::vector< std::pair<int, int> >& queries) {
    int n = input.size();
    int m = queries.size();

    for (int i = 0; i < m; i++) {
        previous[i] = head[queries[i].second];
        head[queries[i].second] = i;
    }
    std::vector<int> output(m);
    std::stack<int> st;

    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)];
        }
    }

    return output;
}

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

    int n, m;
    fin >> n >> m;


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

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


    output = rmq(a, queries);


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

    return 0;
}