// 28-5-7: Magická operace (rychlé řešení)
// Autor: Medvěd

#include <assert.h>

#include "magic.h"

// Maximální počet prvků a úrovní rekurze
#define MAX 1000000
#define MAXL 20

int *nums;		// Posloupnost na vstupu
int len;		// Její délka
int p[MAXL][MAX];	// Jednotlivá patra stromu rekurze

// Předvýpočet
void precalc(int l, int i, int j)
{
	assert(i <= j);
	if (i == j)
		return;
	int s = (i+j)/2;
	p[l][s] = nums[s];
	for (int k=s-1; k>=i; k--)
		p[l][k] = magic_op(nums[k], p[l][k+1]);
	p[l][s+1] = nums[s+1];
	for (int k=s+2; k<=j; k++)
		p[l][k] = magic_op(p[l][k-1], nums[k]);
	precalc(l+1, i, s);
	precalc(l+1, s+1, j);
}

// Dotaz
int query(int l, int i, int j, int qi, int qj)
{
	assert(i <= j);
	assert(i <= qi && qi <= qj && qj <= j);
	if (i == j)
		return nums[i];
	int s = (i+j)/2;
	if (qj <= s)
		return query(l+1, i, s, qi, qj);
	if (qi > s)
		return query(l+1, s+1, j, qi, qj);
	return magic_op(p[l][qi], p[l][qj]);
}

// Hlavní program
int main(void) {
	magic_init();
	magic_get_numbers(&nums, &len);
	precalc(0, 0, len-1);
	magic_begin();

	for (int i=0; i<magic_num_queries(); i++) {
		magic_query q = magic_get_query();
		magic_answer(query(0, 0, len-1, q.from, q.to));
	}

	magic_cleanup();
	return 0;
}