// #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";
	}
}


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();

    // Divide the vector in sqrt blocks of sqrt size
    int sqrtSize = floor(sqrt(noElements));

    // Create the vector
    std::vector<int> minSqrt;
    for (int i = 0; (i + 1) * sqrtSize <= noElements; i++) {
    	minSqrt.push_back(INT_MAX);

    	// Calculate the min elem from current sqrt part
    	for (int j = i * sqrtSize; j < (i + 1) * sqrtSize; j++) {
    		minSqrt[i] = std::min(input[j],minSqrt[i]);
    	}
    }

    // std::cout << "sqrt size: " << sqrtSize << '\n';
    // Get the result of queries
    int noQueries = queries.size();
    for (int i = 0; i < noQueries; i++) {
    	int minElem = INT_MAX;
    	int left = queries[i].first;
    	int right = queries[i].second;
    	left--;
    	right--;
    	// std::cout << "Queri-ul nr: " << i + 1 << '\n';
    	// std::cout << "left: " << left << "   right: " << right << '\n';

    	int leftSqrt = left / sqrtSize;
    	if (left % sqrtSize != 0) {
    		leftSqrt++;
    	}

    	int rightSqrt = (right + 1) / sqrtSize;
    	rightSqrt--;

    	// std::cout << "leftS: " << leftSqrt << "   rightS: " << rightSqrt << '\n';

    	// Check from left to first sqrt block
    	for (int j = left; j < leftSqrt * sqrtSize; j++) {
    		minElem = std::min(minElem, input[j]);
    	}

    	// Check for all sqrt blocks
    	for (int j = leftSqrt; j <= rightSqrt; j++) {
    		minElem = std::min(minElem, minSqrt[j]);
    	}

    	// Check from right to last sqrt block
    	for (int j = rightSqrt * sqrtSize; j <= right; j++) {
    		minElem = std::min(minElem, input[j]);
    	}

    	results.push_back(minElem);
    }

    return results;
}

int main(int argc, char const *argv[])
{
	// std::cout << "MERGE!\n";
	// input vector
	std::vector<int> input;

	// queries
	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;
}