// rmq offline in Nlog*

#include <bits/stdc++.h>

using namespace std;

ifstream fin ("rmq.in"); ofstream fout ("rmq.out");

const int nmax = 1e5;
const int mmax = 1e6;

pair<int, int> st[nmax + 1];
vector<pair<int, int>> q[nmax + 1];
int rasp[mmax + 1];

struct dsu {
    int tata[nmax + 1], grad[nmax + 1], mnval[nmax + 1];

    int find_tata (int x) {
        if (x == tata[x]) return x;
        return tata[x] = find_tata(tata[x]);
    }

    void unite (int x, int y) {
        x = find_tata(x); y = find_tata(y);
        if (x == y)
            return ;

        if (grad[x] < grad[y])
            swap(x, y);

        grad[x] += grad[y];
        tata[y] = x;
        mnval[x] = min(mnval[x], mnval[y]);
    }
} p;

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

    for (int i = 1; i <= n; ++ i) {
        fin >> p.mnval[i];
        p.tata[i] = i;
        p.grad[i] = 1;
    }

    for (int i = 1; i <= m; ++ i) {
        int x, y;
        fin >> x >> y;
        q[y].push_back({x, i});
    }

    int top = 0;
    for (int i = 1; i <= n; ++ i) {
        int val = p.mnval[i];
        while (top > 0 && st[top].first >= val) {
            p.unite(i, st[top].second);
            -- top;
        }

        st[++ top] = {val, i};

        for (auto j : q[i])
            rasp[j.second] = p.mnval[p.find_tata(j.first)];
    }

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

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