#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<stack>
#define maxn 4000010

using namespace std;

int read()
{
	int x=0;char ch=getchar();
	while(ch<'0'||ch>'9')ch=getchar();
	while(ch>='0' && ch<='9'){
		x=x*10+ch-'0';
		ch=getchar();
	}
	return x;
}

struct node{
	int data,l,r;
	node(){data=l=r=0;}
}bt[maxn];

void build(int rt,int lc,int rc)
{
	bt[rt].l=lc;
	bt[rt].r=rc;
	if(lc==rc){
		bt[rt].data=read();
		return;
	}
	int mid=(lc+rc)/2;
	build(rt*2,lc,mid);
	build(rt*2+1,mid+1,rc);
	bt[rt].data=max(bt[rt*2].data,bt[rt*2+1].data);
}

int  find(int lc,int rc,int rt)
{
	if(lc<=bt[rt].l && rc>=bt[rt].r) return bt[rt].data;
	int mid=(bt[rt].l+bt[rt].r)/2;
	if(rc<=mid) return find(lc,rc,rt*2);
	if(lc>mid)	return find(lc,rc,rt*2+1);
	return max(find(lc,rc,rt*2),find(lc,rc,rt*2+1));
	
}
void read1()
{
	int n,m;
	n=read();read();
	if(n!=0)build(1,1,n);
	m=read();
	for(int i=1;i<=m;i++){
		int x,t;
		x=read();
		t=read();
		printf("%d\n",find(x,t,1));
	}
}
int main()
{
	freopen("climb.in","r",stdin);
	freopen("climb.out","w",stdout);
	read1();
	return 0;
}