#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++) {
        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) {
//    cout << vec[x] << " " << vec[y] << "\n";
//    cout << index[x] << " " << index[y] << "\n";
//    cout << depth[x] << " " << depth[y] << "\n";
//    cout << "\n";

    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);
    }
    int c = (a^b);
    int j = log(c) + 1;
    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);
//    for (int i=1; i<=n; i++) {
//        cout << parinte[i] << " ";
//    }
//    cout << "\n";
//    for (int i=1; i<=n; i++) {
//        cout << index[i] << " ";
//    }
//    cout << "\n";
//    for (int i=1; i<=n; i++) {
//        cout << vec[i] << " ";
//    }
    int x, y;
    while (m--) {
        in >> x >> y;
        out << vec[poz[get_lca(x, y)]] << "\n";
    }
    return 0;
}