#include<stdio.h>
long long a[100001],st[400001],mm,p1,p2,i,n,dr[400001],rint[400001],tot[400001],sol,maxim,S;
long long max(long long q1,long long q2)
{
if (q1>q2) return q1;
return q2;
}
void inita(int nod,int b, int e)
{
if (b==e) {st[nod]=dr[nod]=tot[nod]=rint[nod]=a[b];return;}
else
{
inita(2*nod,b,(b+e)/2);
inita(2*nod+1,(b+e)/2+1,e);
st[nod]=max(st[2*nod],tot[2*nod]+st[2*nod+1]);
dr[nod]=max(dr[2*nod+1],tot[2*nod+1]+dr[2*nod]);
rint[nod]=max(max(rint[2*nod],rint[2*nod+1]),dr[2*nod]+st[2*nod+1]);
tot[nod]=tot[2*nod]+tot[2*nod+1];
}
}
void query(int nod,int b,int e,int s,int d)
{
int secvs,secvd;
if (s<=b&&e<=d)
{
maxim=max(max(S+st[nod],rint[nod]),maxim);
S=max(S+tot[nod],dr[nod]);
return;
}
else
{
int mij=(b+e)/2;
if (s<=mij) query(2*nod,b,(b+e)/2,s,d);
if (mij<d) query(2*nod+1,(b+e)/2+1,e,s,d);
}
}
int main()
{
freopen("sequencequery.in","r",stdin);
freopen("sequencequery.out","w",stdout);
scanf("%lld %lld",&n,&mm);
for(i=1;i<=n;i++)
scanf("%lld",&a[i]);
inita(1,1,n);
for(i=1;i<=mm;i++)
{
scanf("%lld %lld",&p1,&p2);
S=0;
maxim=a[p1];
query(1,1,n,p1,p2);
printf("%lld\n",maxim);
}
return 0;
}