#include <bits/stdc++.h>


using namespace std;
ifstream in("rmq.in");
ofstream out("rmq.out");

#define MAXN 1000005
#define MAXK 25
int n;

int block_size, block_cnt;
vector<vector<int>> adj;
vector<int> first_visit;
vector<int> euler_tour;
vector<int> height;
vector<int> log_2;
vector<int> block_mask;
vector<vector<vector<int>>> blocks;
vector<vector<int>> st;

void dfs(int node, int parent, int h) {
    first_visit[node] = euler_tour.size();
    euler_tour.push_back(node);
    height[node] = h;

    for (int child : adj[node]) {
        if (child == parent) {
            continue;
        }
        dfs(child, node, h + 1);
        euler_tour.push_back(node);
    }
}

int min_by_h(int i, int j) {
    return height[euler_tour[i]] < height[euler_tour[j]] ? i : j;
}

int lca_in_block(int b, int l, int r) {
    return blocks[block_mask[b]][l][r] + b * block_size;
}

int lca(int v, int u) {
    int l = first_visit[v];
    int r = first_visit[u];
    if (l > r)
        swap(l, r);
    int bl = l / block_size;
    int br = r / block_size;
    if (bl == br)
        return euler_tour[lca_in_block(bl, l % block_size, r % block_size)];
    int ans1 = lca_in_block(bl, l % block_size, block_size - 1);
    int ans2 = lca_in_block(br, 0, r % block_size);
    int ans = min_by_h(ans1, ans2);
    if (bl + 1 < br) {
        int l = log_2[br - bl - 1];
        int ans3 = st[bl+1][l];
        int ans4 = st[br - (1 << l)][l];
        ans = min_by_h(ans, min_by_h(ans3, ans4));
    }
    return euler_tour[ans];
}

std::vector<int> rmq(const std::vector<int> &input,
                     const std::vector< std::pair<int, int> > &queries)
{
    n = input.size(); // input size
    std::vector<int> ans; // return vector
    ans.reserve(queries.size());

    // build cartesian tree
    vector<int> parent(n, -1);
    adj.resize(n);
    
    // get parents
    stack<int> s;
    for (int i = 0; i < n; i++) {
        int last = -1;
        while (!s.empty() && input[s.top()] >= input[i]) {
            last = s.top();
            s.pop();
        }
        if (!s.empty()) {
            parent[i] = s.top();
        }

        if (last >= 0) {
            parent[last] = i;
        }
        s.push(i);
    }

    // transform from parent array to adjacency list
    int dfs_starting_node;
    for(int i = 0; i < n; ++i) {
        if(parent[i] != -1) {
            adj[i].push_back(parent[i]);
            adj[parent[i]].push_back(i);
        } else {
            dfs_starting_node = i;
        }
    }

    // make euler tour
    first_visit.assign(n, -1);
    height.assign(n, 0);
    euler_tour.reserve(2 * n);
    dfs(dfs_starting_node, -1, 0);

    // precompute all log values
    int m = euler_tour.size();
    log_2.reserve(m + 1);
    log_2.push_back(-1);
    for (int i = 1; i <= m; i++)
        log_2.push_back(log_2[i / 2] + 1);

    block_size = max(1, log_2[m] / 2);
    block_cnt = (m + block_size - 1) / block_size;

    // precompute minimum of each block and build sparse table
    st.assign(block_cnt, vector<int>(log_2[block_cnt] + 1));
    for (int i = 0, j = 0, b = 0; i < m; i++, j++) {
        if (j == block_size)
            j = 0, b++;
        if (j == 0 || min_by_h(i, st[b][0]) == i)
            st[b][0] = i;
    }
    for (int l = 1; l <= log_2[block_cnt]; l++) {
        for (int i = 0; i < block_cnt; i++) {
            int ni = i + (1 << (l - 1));
            if (ni >= block_cnt)
                st[i][l] = st[i][l-1];
            else
                st[i][l] = min_by_h(st[i][l-1], st[ni][l-1]);
        }
    }

    // precompute mask for each block
    block_mask.assign(block_cnt, 0);
    for (int i = 0, j = 0, b = 0; i < m; i++, j++) {
        if (j == block_size)
            j = 0, b++;
        if (j > 0 && (i >= m || min_by_h(i - 1, i) == i - 1))
            block_mask[b] += 1 << (j - 1);
    }

    // precompute RMQ for each unique block
    int possibilities = 1 << (block_size - 1);
    blocks.resize(possibilities);
    for (int b = 0; b < block_cnt; b++) {
        int mask = block_mask[b];
        if (!blocks[mask].empty())
            continue;
        blocks[mask].assign(block_size, vector<int>(block_size));
        for (int l = 0; l < block_size; l++) {
            blocks[mask][l][l] = l;
            for (int r = l + 1; r < block_size; r++) {
                blocks[mask][l][r] = blocks[mask][l][r - 1];
                if (b * block_size + r < m)
                    blocks[mask][l][r] = min_by_h(b * block_size + blocks[mask][l][r], 
                            b * block_size + r) - b * block_size;
            }
        }
    }

    for(std::pair<int, int> q : queries) {
        int left = q.first, right = q.second;
        int res = lca(left, right);
        ans.push_back(input[res]);
    }
    return ans;

}

int main()
{
    int n, q;
    in >> n >> q;
    vector<int> input;
    input.reserve(n);
    vector<pair<int, int>> queries;
    queries.reserve(q);
    for(int i = 0; i < n; ++i) {
        int t;
        in >> t;
        input.push_back(t);
    }

    for(int i = 0; i < q; ++i) {
        int l, r;
        in >> l >> r;
        queries.push_back(make_pair(l - 1, r - 1));
    }

    vector<int> ans = rmq(input, queries);

    for(int i : ans) {
        out << i << "\n";
    }

}