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

using namespace std;

class RMQ {
private:
    int N, log;
    vector<vector<int>> sv;
    vector<int> v;

    int min_v(int a, int b) {
        return v[a] <= v[b] ? a : b;
    }
public:
    RMQ(){}

    RMQ(vector<int> _) {
        v = _;
        N = _.size();
        sv.push_back(v);

        for (int l = 1; (1 << l) <= N; l++) {
            sv.push_back(vector<int>(N - (1 << l) + 1));
            for (int i = 0; i <= N - (1 << l); i++)
                sv[l][i] = min(sv[l-1][i], sv[l-1][i+(1<<(l-1))]);
        }
    }
    int query(int l, int r) {
        if (l > r)
            return 1e9;

        int i = 0;
        while ((2 << i) <= r - l)
            i++;
        return min(sv[i][l], sv[i][r - (1<<i) + 1]);
    }
};

vector<int> A;

class RMQfast {
private:
    int N, M, l;

    vector<int> left, right;

    vector<int> lin, pos;

    vector<int> b_min, b_id;
    RMQ rb;

    vector<short> ans;

    void dfs(int u) {
        pos[u] = lin.size();
        lin.push_back(u);

        if (left[u] != -1) {
            dfs(left[u]);
            lin.push_back(u);
        }
        if (right[u] != -1) {
            dfs(right[u]);
            lin.push_back(u);
        }
    }


public:
    RMQfast() {
        N = A.size();

        left = vector<int>(N, -1);
        right = vector<int>(N, -1);
        vector<int> st;
        for (int i = 0; i < N; i++) {
            int top = -1;
            while (st.size() && A[st.back()] > A[i]) {
                top = st.back();
                st.pop_back();
            }
            if (top != -1)
                left[i] = top;
            if (st.size())
                right[st.back()] = i;
            st.push_back(i);
        }

        int root = st[0];

        pos = vector<int>(N, 0);
        dfs(root);

        M = lin.size();
        l = 2;
        while ((2 << l) < M)
            l++;
        l /= 2;

        while (M % l) {
            lin.push_back(lin.back());
            M++;
        }

        int c = 0, mn = 1e9, p, id = 0;
        for (int i = 0; i < M; i++) {
            int r = (i == 0 || A[lin[i]] > A[lin[i-1]] || A[lin[i]] == A[lin[i-1]] && lin[i] > lin[i-1]);
            id += (r << (i % l));
            mn = min(mn, A[lin[i]]);

            if (i % l == l - 1) {
                b_min.push_back(mn);
                b_id.push_back(id);
                id = 0;
                mn = 1e9;
            }
        }

        rb = RMQ(b_min);

        ans = vector<short>((1 << l) * l * l, -1);
        for (int mask = 0; mask < (1 << l); mask++) {
            vector<int> a(l, 0);
            for (int i = 0; i < l; i++)
                a[i] = ((mask >> i) & 1) * 2 - 1;

            for (int i = 1; i < l; i++)
                a[i] += a[i - 1];

            for (int i = 0; i < l; i++) {
                int mn = i;
                for (int j = i; j < l; j++) {
                    if (a[j] < a[mn]) {
                        mn = j;
                    }
                    ans[mask * l * l + i * l + j] = mn;
                }
            }
        }
    }

    int query(int lf, int rg) {
        lf = pos[lf];
        rg = pos[rg];
        if (lf > rg)
            swap (lf, rg);

        if (lf / l == rg / l) {
            return A[lin[lf / l * l + ans[b_id[lf / l] * l * l + lf % l * l + rg % l]]];
        } else {
            int mn = rb.query(lf / l + 1, rg / l - 1);
            mn = min(mn, A[lin[lf / l * l + ans[b_id[lf / l] * l * l + lf % l * l + l-1]]]);
            mn = min(mn, A[lin[rg / l * l + ans[b_id[rg / l] * l * l + rg % l]]]);
            return mn;
        }
    }
};


int main() {
    ifstream cin("rmq.in");
    ofstream cout("rmq.out");

    int n, q, l, r;
    cin >> n >> q;

    A = vector<int>(n, 0);

    for (int i = 0; i < n; i++)
        cin >> A[i];

    RMQfast rmq = RMQfast();

    for (int i = 0; i < q; i++) {
        cin >> l >> r;
        cout << rmq.query(l - 1, r - 1) << '\n';
    }

    return 0;
}