#include<cstdio>
using namespace std;
int i,n,m,val,a1,b1;
long long maxi,s1,s[300002],a[300002],b[300002],c[300002];
int max(int a,int b)
{
if(a>b) return a;
return b;
}
void update(int nod,int st,int dr,int poz,int val)
{
if(st==dr)
{
s[nod]=val;
a[nod]=val;
b[nod]=val;
c[nod]=val;
return ;
}
int mij=(st+dr)/2;
if(poz<=mij)
update(nod*2,st,mij,poz,val);
else
update(nod*2+1,mij+1,dr,poz,val);
s[nod]=s[nod*2]+s[nod*2+1];
a[nod]=max(a[nod*2],s[nod*2]+a[nod*2+1]);
b[nod]=max(b[nod*2+1],s[nod*2+1]+b[nod*2]);
c[nod]=max(max(c[nod*2],c[nod*2+1]),a[nod*2+1]+b[nod*2]);
}
void query(int nod,int st,int dr,int x,int y)
{
if(x<=st&&dr<=y)
{
maxi=max(maxi,max(c[nod],s1+a[nod]));
s1=max(s1+s[nod],b[nod]);
}
else
{
int mij=(st+dr)/2;
if(x<=mij)
query(nod*2,st,mij,x,y);
if(y>mij)
query(nod*2+1,mij+1,dr,x,y);
}
}
int main()
{
freopen("sequencequery.in","r",stdin);
freopen("sequencequery.out","w",stdout);
scanf("%d",&n);
scanf("%d",&m);
for(i=1;i<=3*n;i++)
{
s[i]=-1000005;
a[i]=-1000005;
b[i]=-1000005;
c[i]=-1000005;
}
for(i=1;i<=n;i++)
{
scanf("%d",&val);
update(1,1,n,i,val);
}
//s1=ce am in dreapta care se termina unde trebuie pana acum,la query
for(i=1;i<=m;i++)
{
scanf("%d",&a1);
scanf("%d",&b1);
maxi=-1000005;
s1=0;
query(1,1,n,a1,b1);
printf("%lld\n",maxi);
}
return 0;
}