#include <cstdio>

#define file_in "sequencequery.in"
#define file_out "sequencequery.out"

#define Nmax 100100
#define Inf 0x3f3f3f3f

int v[Nmax];
int n,m;
int x,y;


int solve(int x, int y)
{
	int i,sum,smax;
	sum=0;
	smax=-Inf;
	for (i=x;i<=y;++i)
	{
		if (sum>=0)
			sum+=v[i];
		else
			sum=v[i];
		if (sum>smax)
			smax=sum;
	}
	
	return  smax;
}

int main()
{
	int i;
	freopen(file_in,"r",stdin);
	freopen(file_out,"w",stdout);
	
	scanf("%d %d", &n,&m);
	for (i=1;i<=n;++i)
		 scanf("%d", &v[i]);
	
	while(m--)
	{
		scanf("%d %d", &x,&y);
		printf("%d\n", solve(x,y));
	}
	
	fclose(stdin);
	fclose(stdout);
	
	return 0;
}