#include<cstdio>
#define NMAX 200005
#define max(a,b)(a>b?a:b)
#define INF -10000000005
using namespace std;
int v[NMAX/2],Max[NMAX*4];
long long sum[NMAX*4],a[NMAX*4],b[NMAX*4],c[NMAX*4];
int n,x,y,i,m,ok;
long long M,S,sol;
void build(int nod,int st,int dr)
{
if (st==dr)
{
a[nod]=b[nod]=c[nod]=max(v[st],0);
sum[nod]=v[st];
Max[nod]=v[st];
}
else
{
int mij=(st+dr)/2;
build(nod*2,st,mij);
build(nod*2+1,mij+1,dr);
a[nod]= max (a[nod*2], a[nod*2+1]+sum[nod*2]);
b[nod]= max (b[nod*2+1], b[nod*2]+sum[nod*2+1]);
c[nod]= max (max(c[nod*2], c[nod*2+1]), b[nod*2]+a[nod*2+1]);
sum[nod]=sum[nod*2]+sum[nod*2+1];
Max[nod]=max(Max[nod*2],Max[nod*2+1]);
}
}
void calculeaza(int nod,int st,int dr)
{
if (x<=st && dr<=y)
{
if (S<0) S=0;
if (sol<max(S+a[nod],c[nod])) {sol=max(S+a[nod],c[nod]);ok=1;}
S=max(S+sum[nod],b[nod]);
if (Max[nod]>M) M=Max[nod];
}
else
{
int mij=(st+dr)/2;
if (x<=mij) calculeaza(nod*2,st,mij);
if (y>mij) calculeaza(nod*2+1,mij+1,dr);
}
}
int main()
{
freopen("sequencequery.in","r",stdin);
freopen("sequencequery.out","w",stdout);
scanf("%d%d",&n,&m);
for (i=1;i<=n;++i)
{
scanf("%d",&v[i]);
}
build(1,1,n);
for (i=1;i<=m;++i)
{
scanf("%d%d",&x,&y);
sol=0;S=0;M=INF;ok=0;
calculeaza(1,1,n);
if (ok==1) printf("%lld\n",sol);
else printf("%lld\n",M);
}
return 0;
}