#include "pch.h"
#include <stdio.h>
#include <cmath>
#include <iostream>
using namespace std;
int *nums, **max, n, deep;

int maxim(int pleft, int pright)
{
	if (pleft == pright) return nums[pleft];
	if (pleft % 2 != 0) return fmax(nums[pleft], maxim(pleft + 1, pright));
	if (pright % 2 == 0) return fmax(nums[pright], maxim(pleft, pright - 1));

	for (int i = deep; i > 0; i--)
	{
		int k = pow(2, i);
		if ((pleft % k == 0) && (pright - pleft >= k - 1)) return fmax(max[i - 1][pleft / k], maxim(pleft + k, pright));
		if (((pright + 1) % k == 0) && (pright - pleft >= k - 1)) return fmax(max[i - 1][(pright + 1) / k - 1], maxim(pleft, pright - k));
	}
}

int main()
{
	scanf_s("%d", &n);
	deep = ceil(log2l(n));
	nums = new int[n];
	max = new int*[deep];
	for (int i = 0; i < n; i++)
	{
		scanf_s("%d", &nums[i]);
	}

	int width = n;
	for (int i = 0; i < deep; i++)
	{
		max[i] = new int[(int)(ceil((double)n / 2))];

		if (i == 0)
		{
			for (int j = 0; j < n; j += 2)
			{
				max[0][(int)(j / 2)] = j + 1 < n ? (int)(fmax(nums[j], nums[j + 1])) : nums[j];
			}
		}
		else
		{
			for (int j = 0; j < width; j += 2)
			{
				max[i][(int)(j / 2)] = j + 1 < n ? (int)(fmax(max[i - 1][j], max[i - 1][j + 1])) : max[i - 1][j];
			}
		}

		width = ceil((double)width / 2);
	}

	int m, templ, tempr;
	scanf_s("%d", &m);
	for (int i = 0; i < m; i++)
	{
		scanf_s("%d%d", &templ, &tempr);
		printf_s("%d ", maxim(templ - 1, tempr - 1));
	}
}