#include<stdio.h>
long n,v[100002],m;
int secv(long p, long k)
	{
	long sc,smax,i;
	sc=v[p];
	smax=v[p];
	for(i=p+1;i<=k;++i)
		{
		if(sc<0) sc=v[i];
		else sc+=v[i];
		if(smax<sc) smax=sc;
		}
	return smax;
	}
void read()
	{
	FILE*f=fopen("sequencequery.in","r");
	FILE*g=fopen("sequencequery.out","w");
	fscanf(f,"%ld %ld",&n,&m);
	long i,p,k;
	long x;
	for(i=1;i<=n;++i) fscanf(f,"%ld",&v[i]);
	for(i=1;i<=m;++i)
		{
		fscanf(f,"%ld %ld",&p,&k);
		x=secv(p,k);
		fprintf(g,"%ld\n",x);
		}
	fclose(f);
	fclose(g);
	}
int main()
	{
	read();
	return 0;
        }