#include<stdio.h>
#include<string.h>
#define inf -100001

long long int A[500000],B[500000],C[500000],Sum[500000],val,poz,start,stop,S,maxim;


inline int max(long long int a,long long int b)
{
	if(a>b)
		return a;
	return b;
}

void update(int nod,int st,int dr)
{
	int div;

	if(st==dr)
	{
		A[nod]=B[nod]=C[nod]=Sum[nod]=val;
		return;
	}

	div=(st+dr)/2;
	if(poz<=div)
		update(2*nod+1,st,div);
	else
		update(2*nod+2,div+1,dr);
	A[nod]=max(A[2*nod+1],Sum[2*nod+1]+A[2*nod+2]);//subsecventa de suma maxima la inceputul intervalului
	B[nod]=max(B[2*nod+2],Sum[2*nod+2]+B[2*nod+1]);//subsecventa de suma maxima la sfarsitul intervalului
	C[nod]=max(B[2*nod+1]+A[2*nod+2],max(C[2*nod+1],C[2*nod+2]));//subsecventa de suma maxima din interval
	Sum[nod]=Sum[2*nod+1]+Sum[2*nod+2];//suma numerelor din interval
}

void query(int nod,int st,int dr)
{
	int div;

	if(start<=st && dr<=stop)
	{
		maxim=max(maxim,max(C[nod],A[nod]+S));
		S=max(S+Sum[nod],B[nod]);
	}
	else
	{
		div=(st+dr)/2;
		if(start<=div)
			query(2*nod+1,st,div);
		if(stop>div)
			query(2*nod+2,div+1,dr);
	}
}

int main()
{
	int n,x,y,i,m;
	FILE *f=fopen("sequencequery.in","r");
	FILE *g=fopen("sequencequery.out","w");

	memset(A,0,sizeof(A));
	memset(B,0,sizeof(B));
	memset(C,0,sizeof(C));
	memset(Sum,0,sizeof(Sum));

	fscanf(f,"%i%i",&n,&m);
	for(i=0;i<n;i++)
	{
		fscanf(f,"%lli",&val);
		poz=i;
		update(0,0,n-1);
	}

	for(i=0;i<m;i++)
	{
		fscanf(f,"%i%i",&x,&y);
		x--;
		y--;
		start=x;
		stop=y;
		maxim=inf;
		S=0;
		query(0,0,n-1);
		fprintf(g,"%lli\n",maxim);
	}
	fclose(f);
	fclose(g);
	return 0;
}