#include <cstdio>
#define filein "sequencequery.in"
#define fileout "sequencequery.out"
#define max(a,b) (a>b)?a:b
using namespace std;

int v[100001];
long long s[100001];
int n,m;

int main()
{
    FILE *in,*out;
    in=fopen(filein,"r");
    out=fopen(fileout,"w");
    fscanf(in,"%d %d",&n,&m);
    int i,j,x1,x2;
    long long smax;
    for (i=1; i<=n; i++)
        fscanf(in,"%d",v+i);
    for (i=1; i<=m; i++)
    {
        fscanf(in,"%d %d",&x1,&x2);
        s[x1]=v[x1];
        smax=v[x1];
        for (j=x1+1; j<=x2; j++)
        {
            s[j]=max((long long) (s[j-1]+v[j]),v[j]);
            if (s[j]>smax) smax=s[j];
        }
        fprintf(out,"%d\n",smax);
    }
    fclose(in);
    fclose(out);
    return 0;
}