#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);
//        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++;
//        cerr << "i=" << i << endl;
//        for (int j = l; j <= r; j++)
//            cerr << v[j] << ' ';
//        cerr << endl;
        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, 0);
        dfs(root);

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

        while (M % l) {
            R.push_back(1);
            lin.push_back(0);
            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 (A[lin[i]] < mn) {
                mn = A[lin[i]];
                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 " << b_min.size() << endl;
//        for (int x : b_min)
//            cerr << x << ' ';
//        cerr << endl;


        rb = RMQ(b_min);
//        cerr << pos.size() << endl;
//        for (int i = 0; i < pos.size(); i++)
//            cerr << i << ": " << pos[i] << endl;
//        cerr << lf << ' ' << rg << endl;

        ans = vector<int>((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, bool debug = 0) {
        if (debug) {
            cerr << "l=" << l << endl;
            cerr << lf << ' ' << rg << endl;
        }
        lf = pos[lf];
        rg = pos[rg];
//        cerr << lf << ' ' << rg << endl;
        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 {

//        cerr << "HELLOO " << l << ' ' << lf / l + 1 << " " << rg / l - 1 << endl;
            int mn = rb.query(lf / l + 1, rg / l - 1);
            if (debug) {
                cerr << "lf: " << lf << endl;
                cerr << "rg: " << rg << endl;
                for (int i = lf; i <= rg; i++)
                    cerr << A[lin[i]] << "-+"[R[i]] << ' ';
                cerr << endl;
                cerr << "min-ints: " << mn << endl;
                cerr << "min-st: " << A[lin[lf / l * l + ans[b_id[lf / l] * l * l + lf % l * l + l-1]]] << endl;
                cerr << "min-dr: " << A[lin[rg / l * l + ans[b_id[rg / l] * l * l + rg % l]]] << endl;
                cerr << "bid-dr: " << b_id[rg / l] << endl;
                cerr << "ans-dr: " << ans[b_id[rg / l] * l * l + 1] << endl;
            }

            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;

    vector<int> v(n, 0);

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

    RMQfast rmq(v);

    for (int i = 0; i < q; i++) {
        cin >> l >> r;
        cout << rmq.query(l - 1, r - 1) << '\n';
//        int a;
//        ok >> a;
//        if (rmq.query(l - 1, r - 1) != a) {
//            int as = rmq.query(l - 1, r - 1, 1);
//            cerr << i << ':' << a << ' ' << as << ':' << l << '-' << r << '\n';
//        }
    }

    return 0;
}