分块 50pts

#define LOCAL
#pragma GCC optimize(2)
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <cmath>
#include <ctime>
#include <cstdlib>
#include <string>
#include <cstring>
#define up(i,x,y) for(int i=x;i<=y;++i)
#define down(i,x,y) for(int i=x;i>=y;--i)
#define lb(x) x&-x

#define wb(x,l) (int)ceil(x/l)
#define br(b,l) l*b
#define bl(b,l) br(b,l)-l+1

using namespace std;
const int maxn=1e6+5;
const int maxr=1e3+5;
const int inf=-1;//因为要找最大值

int a[maxn],block[maxr];
int n,m,l;

inline int read();

int getmax(int x,int y) {
	int res=inf;
	if(x>y) swap(x,y);
	if(y-x<=l) {
		up(i,x,y) res=max(res,a[i]);
		return res;
	}
	int l_=wb(x,l)+1,r_=wb(y,l)-1;
	int x_=bl(l_,l),y_=br(r_,l);
	up(i,l_,r_) res=max(res,block[i]);
	up(i,x,x_+5) res=max(res,a[i]);
	up(i,y_-5,y) res=max(res,a[i]);
	return res;
}

int main() {
#ifdef LOCAL
	freopen("testdata.in","r",stdin);
#endif
	n=read(),m=read();
	l=ceil(sqrt(n+0.5));
	up(i,1,n) {
		a[i]=read();
		block[wb(i,l)]=max(block[wb(i,l)],a[i]);
	}
	int x,y;
	up(i,1,m) {
		x=read(),y=read();
		printf("%d\n",getmax(x,y));
	}
#ifdef LOCAL
	fclose(stdin);
#endif
	return 0;
}

inline int read() {
	int x=0,w=1;
	char ch=0;
	while(ch<'0'||ch>'9') {
		if(ch=='-') w=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
		x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
	return x*w;
}