#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#include<iostream>
inline int max(int a,int b)
{
	return a > b ? a : b; 
}
struct linetree{
	int a[10000000];
	linetree(){memset(a,0,sizeof(a));}
	void build(int root,int l,int r)
	{
		if(l==r){scanf("%d",&a[root]);return;}
		int mid=((l+r)>>1);
		build(root<<1,l,mid);
		build(root<<1|1,mid+1,r);
		a[root]=max(a[root<<1],a[root<<1|1]);
	}
	int answer(int root,int l,int r,int ansl,int ansr)
	{
		if(ansl<=l&&ansr>=r){return a[root];}
		int mid=((l+r)>>1);
		if(ansr<=mid)return answer(root<<1,l,mid,ansl,ansr);
		else if(ansl>mid)return answer(root<<1|1,mid+1,r,ansl,ansr);
		else return max
		(answer(root<<1,l,mid,ansl,ansr), 
		 answer(root<<1|1,mid+1,r,ansl,ansr));
	}
	inline void watch(int n)
	{
		for(int i=1;i<=n*3+1;i++)
		printf("n=%d i=%d a[i]=%d\n",n,i,a[i]);
	}
	inline void error(int i)
	{
		printf("这里有问题>>>%d<<<\n",i); 
	}
}arcv;
int main()
{
	freopen("climb.in","r",stdin);
	freopen("climb.out","w",stdout);
	int n,m,a,b;
	scanf("%d",&n);
	arcv.build(1,0,n);
	//arcv.watch(n);
	scanf("%d",&m);
	for(int i=1;i<=m;i++)
	{
		//arcv.error(m);
		scanf("%d %d",&a,&b);
		printf("%d\n",arcv.answer(1,0,n,a,b));
	}
	fclose(stdin);fclose(stdout);
	return 0;
}