#include <iostream>
#include <fstream>
#define nmax 100002
#define inf 10000000001
using namespace std;
struct arbore_intervale{
long long ssm,spref,ssuf;
};
arbore_intervale aint[10*nmax];
int n,m,v[nmax];
ifstream f("sequencequery.in");
ofstream g("sequencequery.out");
void build(int nod,int st,int dr)///build in O(nlogn)->T(n)=2*T(n/2)+0(n) recombinarea
{
if(st>dr)
return;
if(st==dr)
{
aint[nod].ssm=v[st];
aint[nod].spref=0;
aint[nod].ssuf=0;
return;
}
int mid=(st+dr)>>1;
build(2*nod,st,mid);
build(2*nod+1,mid+1,dr);
int ans=0,k=mid,l=mid+1;
long long bestl=-inf,bestk=-inf,suml=0,sumk=0;
if(aint[2*nod].ssm>aint[nod].ssm)
{
aint[nod].ssm=aint[2*nod].ssm;
ans=1;
}
if(aint[2*nod+1].ssm>aint[nod].ssm)
{
aint[nod].ssm=aint[2*nod+1].ssm;
ans=2;
}
for(int i=mid;i>=st;i--)
{
sumk+=v[i];
if(sumk>bestk)
{
bestk=sumk;
k=i;
}
}
for(int i=mid+1;i<=dr;i++)
{
suml+=v[i];
if(suml>bestl)
{
bestl=suml;
l=i;
}
}
if(bestk+bestl>aint[nod].ssm)
{
aint[nod].ssm=bestk+bestl;
ans=3;
}
switch(ans)
{
case 1:{
aint[nod].spref=aint[2*nod].spref;
aint[nod].ssuf=aint[2*nod].ssuf+aint[2*nod+1].spref+aint[2*nod+1].ssm+aint[2*nod+1].ssuf;
}break;
case 2:{
aint[nod].ssuf=aint[2*nod+1].ssuf;
aint[nod].spref=aint[2*nod].spref+aint[2*nod].ssm+aint[2*nod].ssuf+aint[2*nod+1].spref;
}break;
case 3:{
long long sl=0,sk=0;
for(int i=st;i<k;i++)
sk+=v[i];
for(int i=l+1;i<=dr;i++)
sl+=v[i];
aint[nod].spref=sk;
aint[nod].ssuf=sl;
}break;
}
}
void query(int nod,int st,int dr,int a,int b,long long&dp,long long&sufix,long long&smax)
{
if(st>dr)
return;
if(dr<a||st>b)
return;
if(a<=st&&dr<=b)
{
long long dpcurr;
dpcurr=aint[nod].ssm;
long long add=aint[nod].spref+sufix+dp;
if(add>0)
{
dpcurr+=add;
}
if(dpcurr>smax)
smax=dpcurr;
dp=dpcurr;
sufix=aint[nod].ssuf;
return;
}
int mid=(st+dr)>>1;
query(2*nod,st,mid,a,b,dp,sufix,smax);
query(2*nod+1,mid+1,dr,a,b,dp,sufix,smax);
}
int main()
{
f>>n>>m;
for(int i=1;i<=n;i++)
f>>v[i];
for(int i=1;i<=10*n;i++)
aint[i].ssm=aint[i].spref=aint[i].ssuf=-inf;
build(1,1,n);
for(int i=1;i<=m;i++)
{
int a,b;
long long smax=-inf,dpcurr=0,sufix=0;
f>>a>>b;
query(1,1,n,a,b,dpcurr,sufix,smax);
g<<smax<<"\n";
}
return 0;
}