# include <stdio.h>

# define  _fin  "sequencequery.in"
# define  _fout "sequencequery.out"

# define  myint	long long

# 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("%lld%lld", &n, &m), i=1; i<=n; i++) scanf("%lld", v+i);
	
	update(1, n, 1);
	
	for (step=1; step<=m; step++) {
		scanf("%lld%lld", &ia, &ib);
		query(ia, ib);
		printf("%lld\n", smax);
	}
	
	return 0;
}