#include<stdio.h>
FILE *f=fopen("sequencequery.in","r");
FILE *g=fopen("sequencequery.out","w");
int ssm(int x,int y,int v[])
{
	int min=0,best,max=-100001,ant=0;
	for(x;x<=y;x++)
	{
		ant=v[x]+ant;
		best=ant-min;
		if(ant<min)
			min=ant;
		if(best>max)
			max=best;
	}
	return max;
}
int main()
{
	int n,m,v[100001],x,y,i;
	v[0]=0;
	fscanf(f,"%d %d",&n,&m);
	for(i=1;i<=n;i++)
		fscanf(f,"%d",&v[i]);
	
	for(i=1;i<=m;i++)
	{
		fscanf(f,"%d %d",&x,&y);
		fprintf(g,"%d\n",ssm(x,y,v));
	}
}