//最大值线段树
#include<iostream>
#include<stdio.h>
using namespace std;
const int maxn=1000000+10;
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
 
int te[maxn<<2]={0};
 
void build(int,int,int);
int Query(int,int,int,int,int);
 
int main()
{
	freopen("climb.in","r",stdin);
	freopen("climb.out","w",stdout);
	int n,nouse;
	scanf("%d%d",&n,&nouse);
	build(1,1,n);
	int m;
	scanf("%d",&m);
	for(int i=1;i<=m;++i)
	{
		int l,r;
		scanf("%d%d",&l,&r);
		printf("%d\n",Query(1,1,n,l,r));
	}
	fclose(stdin);fclose(stdout);
	return 0;
}
void build(int rt,int l,int r)
{
	if(l==r){scanf("%d",&te[rt]);return;}
	int mid=(l+r)>>1;
	build(lson);build(rson);
	te[rt]=(te[rt<<1]>te[rt<<1|1]?te[rt<<1]:te[rt<<1|1]);
}
int Query(int rt,int l,int r,int s,int t)
{
	if(s<=l&&t>=r)return te[rt];
	int mid=(l+r)>>1;
	if(t<=mid)return Query(lson,s,t);
	if(s>mid)return Query(rson,s,t);
	int x=Query(lson,s,t),y=Query(rson,s,t);
	return x>y?x:y;
}