#include<stdio.h>
#define inf 0x3f3f3f3f
#define max(a,b) ((a<b)?b:a)
#define max2(a,b,c) ((a>=b)?((a>=c)?a:c):(b>=c)?b:c)
#define dim 1<<19
struct sol{
long long s,a,b,m;
} s1,s2;
long long A[dim],B[dim],M[dim],S[dim],v[100021];
long long n,m,i,j,l,p,k;
FILE *in,*out;

long long interogare(long long nod,long long st,long long dr,long long a,long long b){
long long mijl;
if(st>=a&&dr<=b){
 s1.m=max2(s1.m,M[nod],s1.b+A[nod]);
 s1.a=max(s1.a,s1.s+A[nod]);
 s1.b=max(B[nod],S[nod]+s1.b);
 s1.s+=S[nod];
}
else{
 mijl=(st+dr)>>1;
  if(a<=mijl)
   interogare(nod<<1,st,mijl,a,b);
  if(b>mijl)
   interogare((nod<<1)+1,mijl+1,dr,a,b);
 }
return s1.m;
}

void actualizare(long long nod,long long st,long long dr,long long a,long long b){
long long mijl;
if(!(st-dr))
 A[nod]=B[nod]=M[nod]=S[nod]=v[dr];
else{
 mijl=(st+dr)>>1;
  if(a<=mijl)
   actualizare(nod<<1,st,mijl,a,b);
  if(b>mijl)
   actualizare((nod<<1)+1,mijl+1,dr,a,b);
 S[nod]=S[nod<<1]+S[(nod<<1)+1];
 A[nod]=max(A[nod<<1],S[nod<<1]+A[(nod<<1)+1]);
 B[nod]=max(B[(nod<<1)+1],S[(nod<<1)+1]+B[nod<<1]);
 M[nod]=max2(M[nod<<1],M[(nod<<1)+1],B[nod<<1]+A[(nod<<1)+1]);
}
}

int main(){
in=fopen("sequencequery.in","rt");
out=fopen("sequencequery.out","wt");
fscanf(in,"%lld%lld",&n,&m);
for(i=1;i<=n;i++)
 fscanf(in,"%lld",&v[i]);
actualizare(1,1,n,1,n);
for(i=1;i<=m;i++){
 fscanf(in,"%lld%lld",&l,&p);
 s1.s=0;s1.a=-inf;s1.b=-inf;s1.m=-inf;
 fprintf(out,"%lld\n",interogare(1,1,n,l,p));
}
return 0;
}