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

using namespace std;

const int MAX_N0 = 25000;
const int MAX_LOG = 15;

const int MAX_N = 1e5;
const int MAX_M = 2e5;
const int MAX_L = 8;

int N, M, L;

int A[MAX_N];
int* left_node;
int* right_node;
int pos[MAX_N];

int lin[MAX_M];

unsigned char b_id[MAX_N0];
int RMQ[MAX_LOG][MAX_N0];

unsigned char ans[(1 << MAX_L) * MAX_L * MAX_L];

void init_rmq(int N0) {
    for (int l = 1; (1 << l) <= N0; l++)
        for (int i = 0; i <= N0 - (1 << l); i++)
            RMQ[l][i] = min(RMQ[l-1][i], RMQ[l-1][i+(1<<(l-1))]);
}

int query_intervals(int l, int r) {
    if (l > r)
        return 1e9;

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

void linearize(int u) {
    pos[u] = M;
    lin[M++] = u;

    if (left_node[u] != -1) {
        linearize(left_node[u]);
        lin[M++] = u;
    }
    if (right_node[u] != -1) {
        linearize(right_node[u]);
        lin[M++] = u;
    }
}

int build_cartesian_tree() {
    left_node = RMQ[0];
    right_node = RMQ[4];

    for (int i = 0; i < N; i++)
        left_node[i] = right_node[i] = -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_node[i] = top;
        if (st.size())
            right_node[st.back()] = i;
        st.push_back(i);
    }

    return st[0];
}

void init_RMQ_fast() {
    int root = build_cartesian_tree();
    linearize(root);

    L = 2;
    while ((2 << L) < M)
        L++;
    L /= 2;

    while (M % L) {
        lin[M] = lin[M - 1];
        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_id[i / L] = id;
            RMQ[0][i / L] = mn;
            id = 0;
            mn = 1e9;
        }
    }

    init_rmq(M / L);

    for (int mask = 0; mask < (1 << L); mask++) {
        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[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 = query_intervals(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 q, l, r;
    cin >> N >> q;

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

    init_RMQ_fast();

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

    return 0;
}