// #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(3 * 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;
}