#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <fstream>
#define inf 1999999999
#define nmax 550001
using namespace std;
char sir[1000000];
int k,val,sum,sol;
long long a[nmax],b[nmax],c[nmax],s[nmax];
int n,m,x,y;
inline long long max(long long z,long long q)
{
if(z>q)return z;
else return q;
return 0;
}
void actualizare(int nod,int st,int dr)
{ int mij;
if(st==dr){
          a[nod]=b[nod]=c[nod]=val;
          s[nod]=val;
          }
else {
     mij=(st+dr)/2;
     if(k<=mij)actualizare(2*nod,st,mij);
        else actualizare(2*nod+1,mij+1,dr);
    a[nod]=max(a[2*nod],s[2*nod]+a[2*nod+1]);
    b[nod]=max(b[2*nod+1],b[2*nod]+s[2*nod+1]);
    c[nod]=max(b[2*nod]+a[2*nod+1],max(c[2*nod],c[2*nod+1]));
    s[nod]=s[2*nod]+s[2*nod+1];
     }
}
void interogare(int nod,int st,int dr)
{ int mij;
if(x<=st&&dr<=y)
            {
           // sum=max(0,sum);
            sol=max(sol,max(sum+a[nod],c[nod]));
            sum=max(sum+s[nod],b[nod]);
            }
        else {
             mij=(st+dr)/2;
             if(x<=mij)interogare(2*nod,st,mij);
             if(mij<y)interogare(2*nod+1,mij+1,dr);
             }
}
int main()
{ char *p;
  int i;
freopen("sequencequery.in","r",stdin);
scanf("%d %d\n",&n,&m);
gets(sir); p=strtok(sir," ");
k=0;
while(p!=NULL)
    {
    ++k; val=strtol(p,NULL,10);
    actualizare(1,1,n);
    p=strtok(NULL," ");
    }
ofstream g("sequencequery.out");
for(i=1;i<=m;++i)
    {
    scanf("%d %d\n",&x,&y);
    sum=0;sol=-inf;
    interogare(1,1,n);
    g<<sol<<"\n";
    }
g.close();
fclose(stdin);
return 0;
}