#include <iostream>
#include <fstream>
#include <stack>
#include <vector>
#include <map>
#include <cmath>

using namespace std;

ifstream in("rmq.in");
ofstream out("rmq.out");

const int dim = 100005;

int n, m, vec[dim], parinte[dim], _left[dim], _right[dim], index[dim], depth[dim];
map<int, int> poz;
vector<int> arbore[dim];

void calcul_cartezian() {
    stack<int> candidati;

    for (int i=1; i<=n; i++) {
        while (!candidati.empty() && vec[candidati.top()] > vec[i]) {
            candidati.pop();
        }
        if (candidati.empty()) {
            _left[i] = -1;
        } else {
            _left[i] = candidati.top();
        }
        candidati.push(i);
    }

    candidati = stack<int>();

    for (int i=n; i>=1; i--) {
        while (!candidati.empty() && vec[candidati.top()] > vec[i]) {
            candidati.pop();
        }
        if (candidati.empty()) {
            _right[i] = -1;
        } else {
            _right[i] = candidati.top();
        }
        candidati.push(i);
    }

    for (int i=1; i<=n; i++) {
        if (vec[_left[i]] <= vec[_right[i]]) {
            parinte[i] = _right[i];
        } else {
            parinte[i] = _left[i];
        }
//        parinte[i] = max(_left[i], _right[i]);
    }
}

void DFS(int nod) {
    int cnt = 0;
    for (auto y:arbore[nod]) {
        depth[y] = depth[nod] + 1;
        index[y] = 2 * index[nod] + cnt;
        poz[2 * index[nod] + cnt] = y;
        DFS(y);
        cnt++;
    }
}

int get_lca(int x, int y) {
    if (depth[x] > depth[y]) swap(x, y);

    int a = index[x];
    int b = index[y];

    int depth_diff = depth[y] - depth[x];
    if (depth_diff > 0) {
        b = (b>>depth_diff);
    }
    if (a == b) return a;
    int c = (a^b);

    int j = 0;
    for (int i=31; i>=0; i--) {
        if ((c&(1<<i)) != 0) {
            j = i;
            break;
        }
    }
    j++;
    return (a >> j);
}

int main() {
    in >> n >> m;
    for (int i=1; i<=n; i++) {
        in >> vec[i];
    }
    calcul_cartezian();
    int root;
    for (int i=1; i<=n; i++) {
        if (parinte[i] == -1) root = i;
    }
    index[root] = 1;
    poz[1] = root;
    for (int i=1; i<=n; i++) {
        if (parinte[i] != -1) {
            arbore[parinte[i]].push_back(i);
        }
    }
    DFS(root);
    int x, y;
    while (m--) {
        in >> x >> y;
        out << vec[poz[get_lca(x, y)]] << "\n";
    }
    return 0;
}