#include<stdio.h>
FILE *f=fopen("sequencequery.in","r"),*g=fopen("sequencequery.out","w");

long n,m,x[100001];

int main()
{
fscanf(f,"%ld",&n);
fscanf(f,"%ld",&m);
long i,j,vi,vf,max,sumi;
for(i=1;i<=n;fscanf(f,"%ld",&x[i]),i++);
for(i=1;i<=m;i++)
        {
        fscanf(f,"%ld",&vi);
        fscanf(f,"%ld",&vf);
        sumi=x[vi];
        max=x[vi];
        for(j=vi;j<=vf;j++)
                {
                if(sumi<0)
                        sumi=x[j];
                        else
                        sumi+=x[j];
                if(max<sumi)
                        max=sumi;
                }
        fprintf(g,"%ld\n",max);
        }
fclose(f);
fclose(g);

return 0;
}