#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#include <stdint.h>
#include <math.h>

typedef unsigned int uint;

// Algoritmul Range Minim Query sau RMQ pe scurt este un algoritm ce este folosit
// pentru a determina valoarea minima dintr-un vector pe un interval [x, y], de exemplu:
//    Valoarea minima din vectorul {1, 5, 2, 79, 4} pe intervalul [2, 5](adica minimul
//    dintre elementele de pe indexul 2 si pana la indexul 5) este 2.
// Sunt mai multe moduri in care poate fi implementat acest algoritm, cum ar fi:
//     - Programare dinamica cu co complexitate de O(n^2)
//     - Impartirea in intervale de √n cu o complexitate de O(√n)
// Dar cea mai buna metoda este folosirea unui Sparse Table(ST).
// Compexitatea aceste metode este:
//     - Query-ul se face in O(1)
//     - Preprocesarea/precalcularea se face in O(nlogn)
//     - Spatiu suplimetar necesar este O(nlogn)
// Principiu: Idea este la precalculam minimul tuturor submultimilor de dimensiune 2^j cu j
// pornind de la 0 si mergand pana la log(n). Astfel, vom construi un lookup table care va fi
// o matrice de aceasta data, iar lookup[i][j] va fi egal cu indexul minimului submultimii ce incepe de la
// elementul i si de dimensiune 2^j, de exemplu: 
//     lookup[0][3] va fi egal cu indexul minimului submultmii ce incepe de la primul element are dimensiunea 2^3 = 8 elemente

void preprocess(uint **lookup, uint n, uint m, uint *vector, uint size);
uint query(uint **lookup, uint n, uint m, uint *vector, uint l, uint r);
uint **get_lookup(uint size);
void destroy(uint **matrix, uint n);

int main(void)
{
	FILE *in = fopen("rmq.in", "r");
	FILE *out = fopen("rmq.out", "w");
	if(in != NULL && out != NULL)
	{
		uint n, k;
		fscanf(in, "%u%*c%u%*c", &n, &k);
		uint *vector = malloc(sizeof(uint) * n);
		if(vector != NULL)
		{
			uint i = 0;
			for(; i < n; i++)
			{
				uint t;
				fscanf(in, "%u%*c", &t);
				vector[i] = t;
			}
			uint l2 = (uint)log2(n);
			uint **lk = get_lookup(n);
			preprocess(lk, n, l2, vector, n);

			i = 0;
			for(; i < k; i++)
			{
				uint a, b;
				fscanf(in, "%u%*c%u%*c", &a, &b);

				fprintf(out, "%u\n", query(lk, n, l2, vector, a - 1, b - 1));
			}

			destroy(lk, n);
			free(vector);
		}

		fclose(in);
		fclose(out);
	}
	else
	{
		printf("Error\n");
	}

	return 0;
}

// Functia primeste ca argumente de intrare o matrice de nxm si un vector cu dimensiunea sa
// Dupa cum am spus, calculam minimul pe intervale de forma 0 pana la 2^j cu j = 0..log n, deci
// matricea va fi de n linii si log(n) coloane unde n este dimensiunea vectorului
void preprocess(uint **lookup, uint n, uint m, uint *vector, uint size)
{
	// Pentru a umple matricea lookup cu indexul minimului pe fiecare interval [i, 2^j] vom
	// folosi programarea dinamica intr-o maniera bottom up(de jos in sus).

	// Cum am spus, in matrice retinem pentru o valoarea lookup[i][j] indexul celui mai mic elemente
	// ce incepe de la i si are 2^j elemente. Astfel indexul celui mai mic elemente ce incepe de
	// la o pozitie i si are 2^0 elemente, este chiar i, cel mai mic element din intervalul [i, i] este chiar i.
	uint i = 0;
	for(; i < size; i++)
	{
		// Indexul minimului din intervalul [i, i] este i
		lookup[i][0] = i;
	}

	// Apoi calculam minimul incepand de la intervale mici si mergem la intervale mai mari(bottom up)
	// NOTA: (1 << j) este echivalent cu 2^j si este calculat mult mai rapid.

	// Parcurgem matricea pe coloane, ceea ce inseamna ca, calculam indexul celui mai mic element
	// pentru un interval ce incepe pe pozitia i si are 2^j elemente. Adica:
	//   Mai intai vom umple coloane care ne spune pentru indexul celui mai mic element ce incepe
	//   de la i si are 2^1 elemente, apoi cu 2^2 elemente apoi cu 2^3 elemente s.a.m.d cat timp 2^n <= size
	uint j = 1;
	for(; (1 << j) <= size; j++)
	{

		// Pentru fiecare element din vector(i este indexul unui element din vector/pozitia de inceput
		// a intervalului) si cat timp avem un interval ce incepe la pozitia i si are 2^j elemente
		i = 0;
		for(; (i + (1 << j) - 1) < size; i++)
		{
			// Pentru a calcula indexul celui mai mic element ce incepe de la o pozitie i si are
			// 2^j elemente ne folosim de indexul celui mai mic element ce incepe de la i si are 2^(j - 1) elemente.
			// Astfel, daca elementul din vector de pe pozitia celui mai mic element din intervalul: de la i cu 2^(j - 1) elemente
			// este mai mic decat elementul din vector de pe pozitia minimului din intervalul ce incepe de 2^(j - 1) si are j-1 elemente
			// atunci minimul este cel loo
			if(vector[lookup[i][j - 1]] < vector[lookup[i + (1 << (j - 1))][j - 1]])
			{
				lookup[i][j] = lookup[i][j - 1];
			}
			else
			{
				lookup[i][j] = lookup[i + (1 << (j - 1))][j - 1];
			}
		}
	}
}

// Functia returneaza cel mai mic element din intervalul [l, r] din vector
uint query(uint **lookup, uint n, uint m, uint *vector, uint l, uint r)
{
	// Ideea este sa selectam 2 blocuri care sa ocopere in totalitate intervalul [l, r] si sa
	// calculam minimul din aceste blocuri

	// Invata pe derost(verbatim)
	uint k = (uint)log2(r - l + 1);
	if(vector[lookup[l][k]] <= vector[lookup[r - (1 << k) + 1][k]])
	{
		return vector[lookup[l][k]];
	}
	else
	{
		return vector[lookup[r - (1 << k) + 1][k]];
	}
}

// Functia returneaza o matrice cu size linii si log2(size) coloane
uint **get_lookup(uint size)
{
	uint l2 = log2(size);

	uint **matrix = malloc(sizeof(uint *) * size);
	if(matrix != NULL)
	{
		uint i = 0;
		for(; i < size; i++)
		{
			uint *vector = malloc(sizeof(uint) * l2);
			if(vector != NULL)
			{
				matrix[i] = vector;
			}
			else
			{
				printf("failed to init column\n");
			}
		}

		return matrix;
	}
}

void destroy(uint **matrix, uint n)
{
	uint i = 0;
	for(; i < n; i++)
	{
		free(matrix[i]);
	}

	free(matrix);
}