# include <stdio.h>
# define _fin "sequencequery.in"
# define _fout "sequencequery.out"
# define myint int
# define maxn 100001
# define logn 30
# define tree logn*maxn
// arborele de intervale
myint a[tree], b[tree], c[tree], d[tree];
# define nst(x) ( (x)<<1 )
# define ndr(x) ( ((x)<<1)|1 )
# define npr(x) ( (x)>>1 )
myint n, m, v[maxn];
myint i, saux, smax, step, ia, ib;
# define min(x, y) ( (x)<(y) ? (x):(y) )
# define max(x, y) ( (x)>(y) ? (x):(y) )
void update(myint st, myint dr, myint n)
{
if ( st==dr ) {
d[n] = b[n] = c[n] = /*(v[st]<0 ? 0:v[st]),*/ a[n] = v[st];
}
else {
myint m = (st+dr)>>1, l=nst(n), r=ndr(n);
update(st, m, l);
if ( m < dr ) update(m+1, dr, r);
a[n] = a[l] + a[r];
b[n] = a[l] + (b[r]>a[r] ? b[r]:a[r]);
if ( b[l]>b[n] ) b[n]=b[l];
if ( a[l]>b[n] ) b[n]=a[l];
c[n] = a[r] + (c[l]>a[l] ? c[l]:a[l]);
if ( c[r]>c[n] ) c[n]=c[r];
if ( a[r]>c[n] ) c[n]=a[r];
d[n] = max( d[l], d[r] );
if ( a[l]+a[r] > d[n] ) d[n] = a[l]+a[r];
if ( a[l]+b[r] > d[n] ) d[n] = a[l]+b[r];
if ( c[l]+a[r] > d[n] ) d[n] = a[r]+c[l];
if ( c[l]+b[r] > d[n] ) d[n] = c[l]+b[r];
// ...
}
}
myint qa[2*logn], qb[2*logn], qc[2*logn], qd[2*logn], sz;
void qrtree(myint xa, myint xb, myint st, myint dr, myint n)
{
if ( xa<=st && dr<=xb ) {
qa[++sz]=a[n], qb[sz]=b[n], qc[sz]=c[n], qd[sz]=d[n];
}
else {
myint m = ( st+dr ) >> 1;
if ( xa<=m ) qrtree(xa, xb, st , m, nst(n));
if ( m<xb ) qrtree(xa, xb, m+1, dr, ndr(n));
}
}
void query(myint xa, myint xb)
{
sz=0, qrtree(xa, xb, 1, n, 1);
saux = max(qa[1], qc[1]);
if ( saux<0 ) saux=0;
smax = max(qa[1], qd[1]);
/* for (i=2; i<=sz; i++) {
smax = max(smax, qd[i]);
if ( saux+qb[i] > smax ) smax = saux + qb[i];
saux += qa[i];
if ( saux<0 ) saux = max(qa[i], qc[i]);
smax = max(smax, saux);
if ( saux < 0 ) saux=0;
}*/
for (i=2; i<=sz; i++) {
smax = max(smax, qd[i]);
if ( saux+qb[i] > smax ) smax = saux+qb[i];
saux += qa[i];
if ( qa[i] > saux ) saux = qa[i];
if ( qc[i] > saux ) saux = qc[i];
if ( saux < 0 ) saux = 0;
}
}
int main()
{
freopen(_fin, "r", stdin);
freopen(_fout,"w", stdout);
for (scanf("%d%d", &n, &m), i=1; i<=n; i++) scanf("%d", v+i);
update(1, n, 1);
for (step=1; step<=m; step++) {
scanf("%d%d", &ia, &ib);
query(ia, ib);
printf("%d\n", smax);
}
return 0;
}