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

int main()
{
	int n,m,v[100000],i,a,b,sum=0,max,j;

	FILE *f=fopen("sequencequery.in","r");
    	FILE *g=fopen("sequencequery.out","w");

	fscanf(f,"%i %i",&n,&m);
	for(i=0;i<n;i++)
		fscanf(f,"%i",v+i);

	for(i=0;i<m;i++)
	{
		fscanf(f,"%i %i",&a,&b);
		max=inf;
		sum=0;
		for(j=a;j<b;j++)
		{
			if(sum>=0)
				sum+=v[j];
			else
				sum=v[j];
			if(sum>max)
				max=sum;
		}
		fprintf(g,"%i\n",max);
	}
	fclose(f);
	fclose(g);
	return 0;
}