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

    // std::cout << "LOOOG: " << logElem << '\n';

    // 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 + 1];
    }

    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++) {
            // std::cout << "i = " << i << "  j = " << j << '\n';
            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;
    delete log2;
    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;
}