#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <cstdlib>
using namespace std;

const int MAXN=1000010;
const int MAX_INT=0x7fffffff;
//const int MAXT=110;

int trees[MAXN*3];

int build(int d,int l,int r)
{
        if(l==r) 
		{
		    scanf("%d",&trees[d]);
			return trees[d];
		}
        int mid=(l+r)/2;
        int tl=build(d*2,l,mid);
        int tr=build(d*2+1,mid+1,r);
        return trees[d]=max(tl,tr);
}

int qmax(int d,int l,int r,int tl,int tr)
{
        if(tl<=l&&tr>=r) 
		  return trees[d];
        int mid=(l+r)/2;
        if(tr<=mid) 
		  return qmax(d*2,l,mid,tl,tr);
        else if(tl>mid) 
		  return qmax(d*2+1,mid+1,r,tl,tr);
        else
        {
            int t1=qmax(d*2,l,mid,tl,tr);
            int t2=qmax(d*2+1,mid+1,r,tl,tr);
            return max(t1,t2);
        }
}

int main()
{
        freopen("climb.in","r",stdin);
        freopen("climb.out","w",stdout);
        memset(trees,-1,sizeof(trees));
        int n;
		scanf("%d",&n);
        build(1,0,n);
        int q;
		scanf("%d",&q);
        for(int i=0;i<q;i++)
        {
            int tl,tr;
            scanf("%d%d",&tl,&tr);
            int t=qmax(1,0,n,tl,tr);
            printf("%d\n",t);
        }
        return 0;
}