#include <bits/stdc++.h>


int find_root(int value, std::vector<int>& parent) {
    if (parent[value] == -1)
        return value;

    parent[value] = find_root(parent[value], parent);
    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();

    std::vector<int> parent(n, -1);
    std::vector<int> previous(m);
    std::vector<int> head(n, -1);
    std::vector<int> output(m);
    std::stack<int> st;

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

    return output;
}

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

    fin >> n >> m;
    std::vector<int> a(n);

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

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

    std::vector<int> output;
    output = rmq(a, queries);

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

    fin.close();
    fout.close();
    return 0;
}