#include<stdio.h>
#define mare 1<<30
using namespace std;
int n,m,start,finish,v[300010];
long long sum[400070];
long long a[400000],b[400000],c[400000],s,bests;
long long max (long long a, long long b)
{
if(a>b) return a;
return b;
}
void update(int nod, int st, int dr)
{
long m;
m=(st+dr)/2;
if(st==dr)
{
a[nod]=b[nod]=c[nod]=sum[nod]=v[st];
}
else
{
update(2*nod, st, m);
update(2*nod+1, m+1, dr);
a[nod]=max(a[nod*2],sum[nod*2]+a[nod*2+1]);
b[nod]=max(b[nod*2]+sum[nod*2+1],b[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];
}
}
void query(int nod, int st, int dr)
{
long m;
m=(st+dr)/2;
if(start<=st && dr<=finish)
{
bests=max(bests,max(s+a[nod],c[nod]));
s=max(s+sum[nod],b[nod]);
}
else
{ if(start<=m) query(2*nod, st, m);
if(finish>m) query(2*nod+1, m+1, dr);
}
}
int main()
{
long i;
freopen("sequencequery.in","r",stdin);
freopen("sequencequery.out","w",stdout);
scanf("%ld%ld",&n,&m);
for(i=1;i<=n;++i)
scanf("%ld",&v[i]);
update(1,1,n);
for(i=1;i<=m;++i)
{
scanf("%ld%ld",&start,&finish);
bests=s=-mare;
query(1,1,n);
printf("%ld\n",bests);
}
return 0;
}