#include <cstdio>
#include <cstring>
#define inf 1000000000
using namespace std;
int s[300010],v1[300010],v2[300010],v3[300010],n,m,i,x,l,r,sum,maxim,poz;
long long max(long long a,long long b)
{
if(a>b) return a;
else return b;
}
void schimba(int nod,int st,int dr)
{
if(st==dr)
{
s[nod]=x;
v1[nod]=x;
v2[nod]=x;
v3[nod]=x;
return;
}
int mid=(st+dr)/2;
if(poz<=mid) schimba(nod*2,st,mid);
else schimba(nod*2+1,mid+1,dr);
s[nod]=s[nod*2]+s[nod*2+1];
v1[nod]=max(v1[nod*2],s[nod*2]+v1[nod*2+1]);
v2[nod]=max(v2[nod*2+1],s[nod*2+1]+v2[nod*2]);
v3[nod]=max(max(v3[nod*2],v3[nod*2+1]),v2[nod*2]+v1[nod*2+1]);
}
void raspunde(int nod,int st,int dr)
{
if(l<=st && dr<=r)
{
maxim=max(maxim,max(v3[nod],sum+v1[nod]));
sum=max(sum+s[nod],v2[nod]);
return;
}
int mid=(st+dr)/2;
if(l<=mid) raspunde(nod*2,st,mid);
if(r>mid) raspunde(nod*2+1,mid+1,dr);
}
int main()
{
freopen("sequencequery.in", "r", stdin);
freopen("sequencequery.out", "w", stdout);
scanf("%d%d",&n,&m);
memset(v1,-inf,sizeof(v1));
memset(v2,-inf,sizeof(v2));
memset(v3,-inf,sizeof(v3));
for(i=1;i<=n;i++)
{
scanf("%d",&x);
poz=i;
schimba(1,1,n);
}
for(i=1;i<=m;i++)
{
scanf("%d%d",&l,&r);
maxim=-inf;
sum=0;
raspunde(1,1,n);
printf("%d\n",maxim);
}
fclose(stdin);fclose(stdout);
return 0;
}