#include <iostream>
#include <vector>

class RMQ {
public:
    RMQ(int n) {
        this->n = n;
        a = std::vector<int>(n + 1);
        log = std::vector<int>(n + 1);
        height = fill_log(n);
        s.resize(n + 1);
        for (int i = 1; i <= n; ++i) {
            s[i].resize(height + 1);
        }
    }

    int fill_log(int n) {
        log[0] = -1;
        for (int i = 1; i <= n; ++i) {
            log[i] = log[i / 2] + 1;
        }
        return log[n];
    }

    void add_element(int index, int  element) {
        a[index] = element;
    }

    std::pair<int, int> get_min_pair(std::pair<int, int>& lhs, std::pair<int, int>& rhs) {
        if (a[lhs.second] <= a[rhs.first]) {
            return lhs;
        }
        if (a[lhs.first] >= a[rhs.second]) {
            return rhs;
        }
        if (a[lhs.first] <= a[rhs.first]) {
            if (lhs.first != rhs.first) {
                return { lhs.first, rhs.first };
            }
            if (a[lhs.second] <= a[rhs.second]) {
                return lhs;
            }
            return rhs;
        }
        return { rhs.first, lhs.first };
    }


    void fill_s() {
        for (int i = 1; i < n; ++i) {
            if (a[i] < a[i + 1]) {
                s[i][1] = { i, i + 1 };
            }
            else {
                s[i][1] = { i + 1, i };
            }
        }

        for (int j = 2; (1 << j) < n + 1; ++j) {
            for (int i = 1; i + (1 << j) - 1 < n + 1; ++i) {
                s[i][j] = get_min_pair(s[i][j - 1], s[i + (1 << (j - 1))][j - 1]);
            }
        }
    }

    int query(int u, int v) {
        if (u > v) {
            std::swap(u, v);
        }
        int k = log[v - u + 1];
        return a[get_min_pair(s[u][k], s[v - (1 << k) + 1][k]).second];
    }

private:
    std::vector<int>  log;
    std::vector<std::vector<std::pair<int, int>>> s;
    std::vector<int> a;
    int n = 0;
    int height = 0;
};

int main() {
    int n = 0;
    int m = 0;
    int u = 0;
    int v = 0;
    int element = 0;
    std::cin >> n >> m;
    RMQ g(n);

    for (int i = 1; i < n + 1; ++i) {
        std::cin >> element;
        g.add_element(i, element);
    }
    g.fill_s();
    for (int i = 1; i < m + 1; ++i) {
        std::cin >> u >> v;
        std::cout << g.query(u, v);
    }
    return 0;
}