#include<stdio.h>
#define N 100100
long long n,m,init[N],a,b,rez,dif;
struct arbore{
	long long x,y,max,tot;
}nr[3*N];
inline long long maxim(long long aa,long long bb){
	return aa>bb?aa:bb;
}
void construct(long long st,long long dr,long long poz){
	if(st==dr){
		init[st]=poz;
		return;
	}
	long long x=(st+dr)>>1;
	construct(st,x,2*poz);
	construct(x+1,dr,2*poz+1);
}
void update(long long poz){
	while(poz){
		nr[poz].x=maxim(nr[2*poz].x,nr[2*poz].tot+nr[2*poz+1].x);
		nr[poz].y=maxim(nr[2*poz+1].y,nr[2*poz+1].tot+nr[2*poz].y);
		nr[poz].max=maxim(nr[2*poz].max,nr[2*poz+1].max);
		nr[poz].max=maxim(nr[2*poz].y+nr[2*poz+1].x,nr[poz].max);
		nr[poz].tot=nr[2*poz].tot+nr[2*poz+1].tot;
		poz>>=1;
	}
}
void query(long long st, long long dr, long long poz){
	if(st>b || dr<a)
		return;
	if(a<=st && dr<=b){
		rez=maxim(rez,nr[poz].max);
		rez=maxim(rez,dif+nr[poz].x);
		dif=maxim(dif+nr[poz].tot,nr[poz].y);
		return;
	}
	else{
		if(st<dr){
			long long x=(st+dr)>>1;
			query(st,x,2*poz);
			query(x+1,dr,2*poz+1);
		}
	}
}
int main(){
	freopen("sequencequery.in","r",stdin);
	freopen("sequencequery.out","w",stdout);
	int i;
	scanf("%lld%lld",&n,&m);
	construct(1,n,1);
	for(i=1;i<=n;++i){
		scanf("%lld",&a);
		b=init[i];
		nr[b].x=nr[b].y=nr[b].tot=nr[b].max=a;
		update(b>>1);
	}
	
	for(i=0;i<m;++i){
		scanf("%lld%lld",&a,&b);
		rez=dif=-1000000000;
		query(1,n,1);
		printf("%lld\n",rez);
	}
	fclose(stdin);
	fclose(stdout);
	return 0;
}