#include<stdio.h>
#define tmax 100000
#define nmax 100000
#define inf  10000000000LL
#define max(a,b) (((a)>(b))?(a):(b))
long n,m,a[nmax],kmax;
long long sol,s;


struct tree
{
long st,dr,sd,smax;
};

tree t[tmax];

void update(long k,long x,long y,long i,long a)
{
long m,fs,fd;
if (x==y)
   {
    t[k].st=t[k].dr=t[k].sd=t[k].smax=a;
    return;
   }
m=(x+y)>>1;
fs=k<<1;
fd=fs+1;
if (i<=m)
    update(fs,x,m,i,a);
else update(fd,m+1,y,i,a);
t[k].st=max(t[fs].st,t[fs].sd+t[fd].st);
t[k].dr=max(t[fd].dr,t[fd].sd+t[fs].dr);
t[k].sd=t[fs].sd+t[fd].sd;
t[k].smax=max(t[fs].dr+t[fd].st,max(t[fs].smax,t[fd].smax));
}

void read()
{
scanf("%ld%ld",&n,&m);
long i;
for (i=1;i<=n;i++)
    {
     scanf("%ld",&a[i]);
     update(1,1,n,i,a[i]);
    }
}

void query(long k,long x,long y,long p,long q)
{
long m;
if (p<=x && y<=q)
   {
    sol=max(sol,max(t[k].smax,s+t[k].st));
    s=max(t[k].dr,t[k].sd+s);
    return;
   }
m=(x+y)/2;
if (p<=m)
    query(k<<1,x,m,p,q);
if (q>=m+1)
    query((k<<1)+1,m+1,y,p,q);
}

int main()
{
freopen("sequencequery.in","r",stdin);
freopen("sequencequery.out","w",stdout);
read();
long i;
long p,q;
for (i=1;i<=m;i++)
    {
     scanf("%ld%ld",&p,&q);
     sol=-inf;
     s=0;
     query(1,1,n,p,q);
     printf("%lld\n",sol);
    }
return 0;
}