#include <bits/stdc++.h>

using namespace std;

unsigned int N, M, block_size, block_nr, root;
vector<int> euler_representation, level, first_appearance, log_2, block_mask, v, parent;
vector<vector<int>> tree, b;
vector<vector<vector<int>>> blocks;
vector<pair<int, int>> queries;
stack<int> s;

void ReadInput(istream &f) {
    f >> N >> M;

    for(int i = 0; i < N; i++) {
        int x;
        f >> x;
        v.push_back(x);
    }
    for(int i = 0; i < M; i++) {
        int a, b;
        f >> a >> b;
        queries.push_back(make_pair(a, b));
    }
}
void BuildCartesianTree() {
    for (int i = 0; i < N; i++) {
        int last = -1;
        while (!s.empty() && v[s.top()] >= v[i]) {
            last = s.top();
            s.pop();
        }
        if (!s.empty()) {
            parent[i] = s.top();
        }
        if (last >= 0) {
            parent[last] = i;
        }
        s.push(i);
    }
}
void DFS(int node, int source, int crtLevel) {
    euler_representation.push_back(node);
    first_appearance[node] = euler_representation.size() - 1;
    level[node] = crtLevel;


    for(int x : tree[node]) {
        if (x != source) {
            DFS(x, node, crtLevel + 1);

            euler_representation.push_back(node);
        }
    }

}
int min_levelwise(int x, int y) {
    return level[euler_representation[x]] < level[euler_representation[y]] ? x : y;
}
void Precompute() {
    int nr = euler_representation.size();
    log_2.push_back(-1);
    for(int i = 1; i <= nr; i++) {
        log_2.push_back(log_2[i / 2] + 1);
    }

    block_size = max(1, log_2[nr] / 2);
    block_nr = (nr + block_size - 1) / block_size;

    b.assign(block_nr, vector<int>(log_2[block_nr] + 1));
    for(int i = 0, j = 0, block = 0; i < nr; i++, j++) {
        if(j == block_size) {
            block++;
            j = 0;
        }
        if(j == 0 || min_levelwise(b[block][0], i) == i) {
            b[block][0] = i;
        }
    }
    for(int j = 1; j <= log_2[block_nr]; j++) {
        for(int i = 0; i < block_nr; i++) {
            int p = i + (1 << (j - 1));
            if(p >= block_nr) {
                b[i][j] = b[i][j - 1];
            }
            else {
                b[i][j] = min_levelwise(b[i][j - 1], b[p][j - 1]);
            }
        }
    }

    block_mask.assign(block_nr, 0);
    for(int i = 0, j = 0, block = 0; i  < nr; i++, j++) {
        if(j == block_size) {
            j = 0;
            block++;
        }
        if(j > 0 && (i >= nr || min_levelwise(i - 1, i) == i - 1)) {
            block_mask[block] += 1 << (j - 1);
        }
    }

    unsigned int total = 1 << (block_size - 1);
    blocks.resize(total);
    for(int block = 0; block < block_nr; block++) {
        int mask = block_mask[block];
        if(blocks[mask].empty()) {
            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 (block * block_size + r < nr)
                        blocks[mask][l][r] = min_levelwise(block * block_size + blocks[mask][l][r],
                                block * block_size + r) - block * block_size;
                }
            }
        }
    }
}
int LCA_block(int block, int l, int r) {
    return blocks[block_mask[block]][l][r] + block * block_size;
}
int LCA(int x, int y) {
    int l = first_appearance[x];
    int r = first_appearance[y];

    if(l > r) {
        int aux = l;
        l = r;
        r = aux;
    }

    int block_l = l / block_size;
    int block_r = r / block_size;

    if(block_l == block_r) {
        return euler_representation[LCA_block(block_l, l % block_size, r % block_size)];
    }

    int sol1 = LCA_block(block_l, l % block_size, block_size - 1);
    int sol2 = LCA_block(block_r, 0, r % block_size);
    int solution = min_levelwise(sol1, sol2);

    if(block_l + 1 < block_r) {
        int logarithm = log_2[block_r - block_l - 1];
        int sol3 = b[block_l + 1][logarithm];
        int sol4 = b[block_r - (1 << logarithm)][logarithm];
        solution = min_levelwise(solution, min_levelwise(sol3, sol4));
    }
    return euler_representation[solution];
}
void PrintOutput(ostream &g) {
    for(auto p : queries) {
        g << v[LCA(p.first, p.second)] << '\n';
    }
}
void InitializeTree() {
    tree.resize(N);
    for(int i = 0; i < parent.size(); i++) {
        if(parent[i] == -1) {
            root = i;
        }
        else {
            tree[parent[i]].push_back(i);
        }
    }
    first_appearance.resize(N);
    level.resize(N);
}
int main() {
    ifstream f;
    f.open("rmq.in");

    ofstream g;
    g.open("rmq.out");

    ReadInput(f);

    parent.assign(N, -1);
    BuildCartesianTree();

    InitializeTree();

    DFS(root, -1, 0);

    Precompute();

    PrintOutput(g);

    f.close();
    g.close();
    return 0;
}