#include <stdio.h>
#include <algorithm>
#include <climits>
using namespace std;
FILE*f=fopen("sequencequery.in","r");
FILE*g=fopen("sequencequery.out","w");
int main()
{
int j,s,smax,i,nrp,n,v[100001],st[100001],dr[100001];
    v[0]=0;
    fscanf(f,"%d%d",&n,&nrp);
    for(i=1;i<=n;i++) fscanf(f,"%d",&v[i]);
    for(i=1;i<=nrp;i++) fscanf(f,"%d %d",&st[i],&dr[i]);
    for(i=1;i<=nrp;i++){s=0;
    smax=-LONG_MAX;
    for(j=st[i];j<=dr[i];j++){
    s=max(s+v[j],v[j]);
  if(s>smax) smax=s;
    }
fprintf(g,"%d\n",smax);


    }
    fclose(f);
    fclose(g);

    return 0;
}