#include <bits/stdc++.h>
using namespace std;
struct node 
{
	int l,r,mx;
}tree[10000010];
int a[1000010];
void wh(int now)
{
	tree[now].mx=max(tree[now<<1].mx,tree[now<<1|1].mx);
}
void build(int now,int l,int r)
{
	tree[now].l=l;
	tree[now].r=r;
	if (l==r) tree[now].mx=a[l];
	else 
	{
		int mid=(l+r)>>1;
		build(now<<1,l,mid);
		build(now<<1|1,mid+1,r);
		wh(now);
	}
}
int  qurty(int now,int x,int y)
{
	int mx=0;
	if (tree[now].l==x&&tree[now].r==y) mx=max(mx,tree[now].mx);
	else 
	{
		int mid=(tree[now].l+tree[now].r)>>1;
		if (x>=mid+1) mx=max(mx,qurty(now<<1|1,x,y));
		else if (y<=mid) mx=max(mx,qurty(now<<1,x,y));
		     else {
		     	mx=max(qurty(now<<1,x,mid),qurty(now<<1|1,mid+1,y));
		     	
		     }
	}
	return mx;
}
int main()
{
	int n;
	int m;
	freopen("climb.in","r",stdin);
	freopen("climb.out","w",stdout);
	cin>>n;
	//freopen("w.in","r",stdin);
	for (int i=0;i<=n;i++)
		cin>>a[i];
		
	build(1,0,n);
	cin>>m;
	for (int i=1;i<=m;i++)
	{
		int x,y;
		cin>>x>>y;
		cout<<qurty(1,x,y)<<endl;
	}
	return 0;
}