#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}
inline void write(int x){
    if(x==0){putchar('0');return;}
	int len=0,k1=x,c[10005];
	if(k1<0)k1=-k1,putchar('-');
	while(k1)c[len++]=k1%10+'0',k1/=10;
	while(len--)putchar(c[len]);
}
const int N=2e6+5;
int pos[N],st[N],ed[N],maxn[N],add[N],a[N],turn[N];
void upd(int l,int r,int k){
	int p=pos[l],q=pos[r];
	if(p==q){
		for(int i=l;i<=r;i++)a[i]+=k;
		maxn[p]+=k; 
	}
	else{
		for(int i=p+1;i<=q-1;i++)add[i]+=k;
		for(int i=l;i<=ed[p];i++)a[i]+=k;
		maxn[p]+=k;
		for(int i=st[q];i<=r;i++)a[i]+=k;
		maxn[q]+=k;
	}
}
void ask(int l,int r){
	int p=pos[l],q=pos[r];
	int ans=0;
	if(p==q){
		for(int i=l;i<=r;i++)ans=max(a[i]+add[p],ans);
	}
	else{
		for(int i=p+1;i<=q-1;i++)ans=max(maxn[i]+add[i],ans);
		for(int i=l;i<=ed[p];i++)ans=max(a[i]+add[p],ans);
		for(int i=st[q];i<=r;i++)ans=max(a[i]+add[q],ans);
	}
	cout<<ans<<"\n";
} 
signed main(){
	int n=read(),m=read();
	for(int i=1;i<=n;i++)a[i]=read(); 
	int block=sqrt(n);
	int t=n/block;
	if(n%block)t++;
	for(int i=1;i<=t;i++){
		st[i]=(i-1)*block+1;
		ed[i]=i*block; 
	}	
	ed[t]=n;
	for(int i=1;i<=n;i++)pos[i]=(i-1)/block+1;
	for(int i=1;i<=t;i++){
		for(int j=st[i];j<=ed[i];j++){
			maxn[i]=(maxn[i],a[j]);
		}
	}
	for(int i=1;i<=m;i++){
		int x=read(),y=read();
		ask(x,y);
	}
	return 0;
}

没tle，WA了（我就是脑子有点问题）