#include <stdio.h>
#include <climits>
using namespace std;
FILE *fin=fopen("sequencequery.in","r");
FILE *fout=fopen("sequencequery.out","w");
int i,n,m,x,y,a[1001],rez;
int scv(int xx,int yy)
{
    int i=0,s=0,smax=0;
    smax=-LONG_MAX;
    for(i=xx;i<=yy;i++)
    {
        s+=a[i];
        if(s>smax)smax=s;
        if(s<0)s=0;
    }
    return smax;
}
int main()
{
    fscanf(fin,"%d",&n);
    fscanf(fin,"%d",&m);
    for(i=1;i<=n;i++)
        fscanf(fin,"%d",&a[i]);
    for(i=1;i<=m;i++)
    {
        fscanf(fin,"%d%d",&x,&y);
        rez=scv(x,y);
        fprintf(fout,"%d\n",rez);
    }
    return 0;
}