// #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();
    int logElem = (int) log2(noElements);


    // Precalculate the sparse table and log2
    int **sparse_table;
    sparse_table = new int*[noElements];
    for (int i = 0; i < noElements; i++) {
        sparse_table[i] = new int[logElem];
    }

    int *log2;
    log2 = new int[noElements];

    log2[1] = 0;
    sparse_table[0][0] = input[0];
    sparse_table[1][0] = input[1];
    for (int i = 2; i < noElements; i++) {
        sparse_table[i][0] = input[i];
        log2[i] = log2[i / 2] + 1;
    }

    for (int j = 1; (1 << j) <= noElements; j++) {
        for (int i = 0; i + (1 << j) <= noElements; i++) {
            sparse_table[i][j] = std::min(sparse_table[i][j - 1],
                                sparse_table[i + (1 << (j-1))][j - 1]);
        }
    }


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

        // Calculate the lenght of the interval
        int lenght = right - left + 1;
        int power = log2[lenght];

        minElem = std::min(sparse_table[left][power],
                sparse_table[right - (1 << power) + 1][power]);
    	
    	// std::cout << "Result: " << minElem <<"\n\n";
    	results.push_back(minElem);
    }

    for(int i = 0; i < noElements; i++) {
        delete sparse_table[i];
    }
    delete sparse_table;

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