#include <stdio.h>
int arr[50001][20];
int find_num(int n,int m)
{
int big = -1;
int floor=0;
if(n==m)
{
return arr[n][0];
}
while(n<m)
{
if(n%2==1)
{
if(big < arr[n][floor])
{
big = arr[n][floor];
}
n +=1;
}
else if(n%2==0)
{
if(big < arr[n][floor])
{
big = arr[n][floor];
}
n+=2;
}
if(m%2==1)
{
if(big < arr[m][floor])
{
big =arr[m][floor];
}
m-=1;
}
m /= 2;
n /= 2;
floor++;
}
if(big < arr[m][floor])
{
big = arr[m][floor];
}
return big;
}
int main()
{
int n,m,j,i,h;
int size;
int old;
scanf("%d",&n);
size = n;
old = n;
for(i = 1; i <= n; i++)
{
scanf("%d",&arr[i][0]);
}
for(i = 1; size != 1; i++)
{
for(j = 1; j <= size; j++)
{
if(j%2 == 0)
arr[j/2][i] = arr[j][i-1]>arr[j-1][i-1]?arr[j][i-1]:arr[j-1][i-1];
}
if(size%2 == 1)
{
arr[size/2][i] = arr[old][i-1];
}
old = size;
size = (size/2) + (size%2);
}
scanf("%d",&m);
for(i = 0; i < m; i++)
{
scanf("%d%d",&h,&n);
size = find_num(h,n);
printf("%d ",size);
}
}
/**
50000*50000
1
1 2
1 2 34
123 456 78
*/