#include <iostream>
#include <vector>
#include <cstdio>

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);
//        sv.push_back(vector<int>(N));

//        for (int i = 0; i < N; i++)
//            sv[0][i] = v[i];
        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]);
    }
};

class RMQfast {
private:
    int N, M, l;
    vector<int> A;

    vector<int> left, right;

    vector<int> lin, R, pos;

    vector<int> b_min, b_pos, b_id;
    RMQ rb;

    vector<int> ans;

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

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


public:
    RMQfast(vector<int> _) {
        A = _;
        N = _.size();

        vector<int> T(N), 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) {
                T[i] = T[top];
                T[top] = i;
            } else
                T[i] = (st.size() ? st.back() : -1);
            st.push_back(i);
        }

        left = vector<int>(N, -1);
        right = vector<int>(N, -1);
        int root = st[0];

        for (int i = 0; i < N; i++) {
            if (T[i] == -1)
                continue;

            if (T[i] < i)
                right[T[i]] = i;
            else
                left[T[i]] = i;
        }

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

        M = R.size();
        l = 2;
        while ((2 << l) < M)
            l++;
        l /= 2;
//        cerr << l << endl;

        while (M % l) {
            R.push_back(1);
            M++;
        }

        int c = 0, mn = 1e9, p, id = 0;
        for (int i = 0; i < M; i++) {
            c += 2 * R[i] - 1;
            id += (R[i] << (i % l));
            if (c < mn) {
                mn = c;
                p = i;
            }

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

//        cerr << lin.size() << endl;
//        for (int x : lin)
//            cerr << x << ' ';
//        cerr << endl;
//        for (int x : lin)
//            cerr << A[x] << ' ';
//        cerr << endl;
//        cerr << b_min.size() << endl;
//        for (int x : b_min)
//            cerr << x << ' ';
//        cerr << endl;


        rb = RMQ(b_min);

        ans = vector<int>(1 << l);
        for (int mask = 0; mask < (1 << l); mask++) {
            vector<int> a(l);
            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[i] < a[mn]) {
                        mn = i;
                    }
                    ans[mask * l * l + i * l + j] = mn;
                }
            }
        }
    }

    int query(int lf, int rg) {
//            cerr << "HEY" << endl;
        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);
//            cerr << "lf: " << lf << endl;
//            cerr << "rg: " << rg << endl;
//            cerr << "min-ints: " << mn << endl;
//            cerr << "min-st: " << lin[lf / l * l + ans[b_id[lf / l] * l * l + lf % l + l-1]] << endl;
//            cerr << "min-dr: " << lin[rg / l * l + ans[b_id[rg / l] * l * l + rg % l]] << endl;

            mn = min(mn, A[lin[lf / l * l + ans[b_id[lf / l] * l * l + lf % l + l-1]]]);
            mn = min(mn, A[lin[rg / l * l + ans[b_id[rg / l] * l * l + rg % l]]]);
            return mn;
        }
    }
};

int main() {
    freopen("rmq.in", "r", stdin);
//    freopen("rmq.out", "w", stdout);

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

    vector<int> v(n);

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

    RMQfast rmq(v);

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

    return 0;
}