#include<fstream>
#define DIM 100004
using namespace std;
int L[DIM],R[DIM],S[DIM],v[DIM];
int n,m,poz,a,b,s,rez;
void query(int nod,int st,int dr);
void update(int nod,int st,int dr);
int inline maxim(int a,int b);
ofstream fout("sequencequery.out");
int main()
{
ifstream fin("sequencequery.in");
fin>>n>>m;
int i,j;
for(i=1;i<=n;i++)
{
fin>>a;
poz=i;
update(1,1,n);
}
for(i=1;i<=m;i++)
{
fin>>a>>b;
rez=-32423423;
s=0;
query(1,1,n);
fout<<rez<<"\n";
}
return 0;
}
void update(int nod,int st,int dr)
{
if(st==dr)
{
v[nod]=L[nod]=R[nod]=S[nod]=a;
return;
}
else
{
int mij=(st+dr)/2;
if(poz<=mij)
update(2*nod,st,mij);
else
update(2*nod+1,mij+1,dr);
}
L[nod]=maxim(L[2*nod],S[2*nod]+L[2*nod+1]);
R[nod]=maxim(R[2*nod+1],R[2*nod]+S[2*nod+1]);
v[nod]=maxim(maxim(v[2*nod],v[2*nod+1]),R[2*nod]+L[2*nod+1]);
S[nod]=S[2*nod]+S[2*nod+1];
}
void query(int nod,int st,int dr)
{
if(st>=a && dr<=b)
{
rez=maxim(rez,maxim(s+L[nod],v[nod]));
s=maxim(s+S[nod],R[nod]);
return ;
}
else
{
int mij=(st+dr)/2;
if(a<=mij)
query(2*nod,st,mij);
if(b>mij)
query(2*nod+1,mij+1,dr);
}
}
int inline maxim(int a,int b)
{
if(a>b)
return a;
else
return b;
}