// #include "algo.h"
#include <vector>
#include <iostream>
#include <fstream>
#include <string>
#include <math.h>
#include <limits.h>


void read(const std::string& inFilePath, std::vector<int>& input, 
        std::vector< std::pair<int, int> >& queries) {
    // Open the file stream
    std::ifstream inFile(inFilePath);

    if (inFile.is_open()) {
        int noElements = 0;
        inFile >> noElements;

        int noQueries = 0;
        inFile >> noQueries;

        for (int i = 0; i < noElements; i++) {
            int elem;
            inFile >> elem;
            input.push_back(elem);
        }

        for (int i = 0; i < noQueries; i++) {
            int left;
            int right;
            inFile >> left >> right;
            queries.push_back({left, right});
        }
        inFile.close();
    } else {
        std::cout << "ERROR: Unable to open file!\n";
    }
}


void printResult(const std::vector<int>& results,
                const std::string& outFilePath) {
    // Open the file stream
    std::ofstream outFile(outFilePath);

    if (outFile.is_open()) {
        for (int i = 0; i < results.size(); i++) {
            // For each query print the result on a different line.
            outFile << results[i] << '\n';
        }

        outFile.close();
    } else {
        std::cout << "ERROR: Unable to open file!\n";
    }
}

// Updates the node of a given segment tree
void update(int node, int left, int right, int pos,
                int value, std::vector<int>& segTree) {
    if (left == right) {
        segTree[node] = value;
    } else {
        int mid = left +  (right - left) / 2;
 
        if (pos <= mid) {
            update(2 * node, left, mid, pos, value, segTree);
        } else {
            update(2 * node + 1, mid + 1, right, pos, value, segTree);
        }

        segTree[node] = std::min(segTree[2 * node], segTree[2 * node + 1]);
    }
 
}

// Query for a segment tree on interval [start, end]
void query(int node, int left, int right, int start, int end,
                        int &minVal,  std::vector<int> segTree) {
    if (start <= left && right <= end) {
        minVal = std::min(minVal, segTree[node]);
    } else {
        int mid =left + (right - left) / 2;

        if (start <= mid) {
            query(2 * node, left, mid, start, end, minVal, segTree);
        }

        if (end > mid) {
            query(2 * node + 1, mid + 1, right, start, end, minVal, segTree);
        }
    }
}

std::vector<int> rmq(const std::vector<int>& input,
    const std::vector< std::pair<int, int> >& queries) {
    std::vector<int> results;
    int noElements = input.size();

    std::vector<int> segTree(4 * noElements, INT_MAX);

    for (int i = 0; i < noElements; i++) {
        update(1, 1, noElements, i + 1, input[i], segTree);
    }

    // Get the result of queries
    int noQueries = queries.size();
    for (int i = 0; i < noQueries; i++) {
        int minElem = INT_MAX;

        int start = queries[i].first;
        int end = queries[i].second;

        query(1, 1, noElements, start, end, minElem, segTree);

        results.push_back(minElem);
    }

    return results;
}

int main(int argc, char const *argv[])
{
    std::vector<int> input;

    std::vector< std::pair<int, int> > queries;

    read("rmq.in", input, queries);

    std::vector<int> results;
    results = rmq(input, queries);
    printResult(results, "rmq.out");
    return 0;
}