#include <stdio.h>
#include <stdlib.h>
#define MAX 100001
#define in "rmq.in"
#define out "rmq.out"
unsigned int tree[4*MAX];
void insert(unsigned int node, unsigned int left, unsigned int right, unsigned int poz, unsigned int value)
{
unsigned int m;
if (left >= right)
{
tree[node] = value;
}
else
{
m = (left + right) / 2;
if (poz <= m)
insert(2*node, left, m, poz, value);
else
insert(2*node+1, m+1, right, poz, value);
tree[node] = tree[2*node] > tree[2*node+1] ? tree[2*node+1] : tree[2*node];
}
}
unsigned int find(unsigned int node, unsigned int left, unsigned int right, unsigned int a, unsigned int b)
{
unsigned int x = MAX, y = MAX, m;
if (a <= left && b >= right)
return tree[node];
else
{
m = (left + right) / 2;
if (a <= m)
x = find(2*node, left, m, a, b);
if (b > m)
y = find(2 * node + 1, m + 1, right, a, b);
return x < y ? x : y;
}
}
int main()
{
unsigned int a[MAX], i, z, m, x, y, n;
FILE *fin, *fout;
if ((fin = fopen(in, "r")) == NULL)
{
printf("Eroare \n");
exit(-1);
}
//read dimension of vectors
fscanf(fin, "%d%d", &n, &m);
//read the vectors
for (i = 1; i<=n ; i++)
{
fscanf(fin, "%d", &a[i]);
insert(1, 1, n, i, a[i]);
}
fout = fopen(out, "w");
for (i = 0; i <= 4*n+4; i++)
printf("%d ", tree[i]);
printf("\n");
for (i = 0; i < m; i++)
{
fscanf(fin, "%d%d", &x, &y);
//printf("%d %d\n", x, y);
z = find(1, 1, n, x, y);
//printf("%d\n", z);
fprintf(fout, "%d\n", z);
}
fclose(fin);
fclose(fout);
return 0;
}