#include <stdio.h>
#define NM 200010
long v[NM];
long a[NM<<1], b[NM<<1], c[NM<<1], d[NM<<1];
long long s, sol;
long n, m;
//a[i] az i. nodhoz tartozo intervallum osszege
//b[i] az i. nodban levo intervallum maximuma
//c[i] az i. nodban levo intervallum balrol maximuma
//d[i] az i. nodban levo intervallum jobbrol maximuma
inline long max(long a, long b)
{
return a>b?a:b;
}
void build(long nod, long e, long u)
{
if (e==u)
{
a[nod]=b[nod]=c[nod]=d[nod]=v[e];
}
else
{
int mid = (e+u)>>1;
int ie = 2*nod;
int iu = 2*nod+1;
build(ie, e, mid);
build(iu, mid+1, u);
a[nod] = a[ie] + a[iu];
b[nod] = max(max(b[ie],b[iu]), d[ie] + c[iu]);
c[nod] = max(c[ie], a[ie] + c[iu]);
d[nod] = max(d[iu], a[iu] + d[ie]);
}
}
void query(long nod, long e, long u, long i, long j)
{
if (i<=e && u<=j)
{
sol = max(max(s+c[nod],b[nod]), sol);
s = max(s+a[nod], d[nod]); //lol
}
else
{
int mid=(e+u)>>1;
int ie=2*nod;
int iu=2*nod+1;
if (i<=mid) query(ie, e, mid, i, j);
if (mid<j) query(iu, mid+1, u, i, j);
}
}
int main()
{
freopen("sequencequery.in","r",stdin);
freopen("sequencequery.out","w",stdout);
scanf("%d%d", &n, &m);
for (long i=1; i<=n; ++i)
scanf("%d", v+i);
build(1,1,n);
for (long i=1; i<=m; ++i)
{
int x, y;
scanf("%d%d", &x, &y);
sol=v[x]; s=0; query(1,1,n, x, y);
printf("%lld\n", sol);
}
return 0;
}