/*
 * Copyright 2021 - Dumitrescu Alexandra
 * grupa 323, seria CA, ACS UPB
 * Tema #1 - RMQ - Range Minimum Query
 * Noiembrie 2021
 */


#include <stdio.h>
#include <stdlib.h>
#include "./utils/utils.h"
#include "./utils/math_utils.h"

void preprocess(int N, int *v, int **preprocessed_data) {
	int block_size = square_root(N);
	int block_count = square_root(N);

	if(!is_perfect_square(N))
		block_count ++;

	(*preprocessed_data) = malloc(block_count * sizeof(**preprocessed_data));

	int block_minimum, i, j;
	for(i = 0, j = 0; i < N; i++) {
		if(i % block_size == 0) {
			if(i != 0) {
				(*preprocessed_data)[j] = block_minimum;
				j ++;
			}
			block_minimum = v[i];
		}
		if(v[i] < block_minimum)
			block_minimum = v[i];
	}

	if(!is_perfect_square(N)) 
		(*preprocessed_data)[j] = block_minimum;
}


int rmq(int left, int right, int N, int *v, int *preprocessed_data) {
	int block_size = square_root(N);
	int rmq_ans, i, j;

	left --;
	right --;

	if(left == right)
		return v[left];

	rmq_ans = v[left];
	for(i = left; i % block_size != 0 && i < right; i++) {
		if(v[i] < rmq_ans)
			rmq_ans = v[i];
	}

	for(j = i / block_size; i + block_size < right ; i+= block_size, j++) {
		if(i >= right)
			break;
		if(preprocessed_data[j] < rmq_ans)
			rmq_ans = preprocessed_data[j];
	}

	for(j = i; j <= right; j++) {
		if(v[j] < rmq_ans)
			rmq_ans = v[j];
	}

	return rmq_ans;
}


// void get_queries(int N, int *v, int *preprocessed_data) {
// 	int M, left_bound, right_bound;
// 	scanf("%d", &M);
// 	for(int nr_query = 0; nr_query < M; nr_query++) {
// 		scanf("%d %d", &left_bound, &right_bound);
// 		printf("%d\n", rmq(left_bound, right_bound, N, v, preprocessed_data));
// 	}
// }

// void get_data(int *N, int **v) {
// 	scanf("%d", N);
// 	(*v) = malloc((*N) * sizeof(**v));

// 	for(int i = 0; i < *N; i++)
// 		scanf("%d", &((*v)[i]));
// }

int main(void)
{	
	int N, M, *v = NULL, *preprocessed_data = NULL;
	// get_data(&N, &v);
	FILE *in = fopen("rmq.in", "rt");
	FILE *out = fopen("rmq.out", "wt");
	fscanf(in, "%d %d", &N, &M);
	v = malloc(N * sizeof(int));
	for(int i = 0; i < N; i++)
		fscanf(in, "%d", &v[i]);
	

	preprocess(N, v, &preprocessed_data);
	for(int i = 0; i < M; i++)
	{
		int left_b, right_b;
		fscanf(in, "%d %d", &left_b, &right_b);
		fprintf(out, "%d\n", rmq(left_b, right_b, N, v, preprocessed_data));
	}
	// get_queries(N, v, preprocessed_data);
	free(v);
	free(preprocessed_data);
}