# include <stdio.h>

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

# define  maxn  100001
# define  logn	17

# define  tree	logn*maxn


// arborele de intervale
int a[tree], b[tree], c[tree], d[tree];

# define  nst(x) ( (x)<<1 )
# define  ndr(x) ( ((x)<<1)|1 )
# define  npr(x) ( (x)>>1 )

int n, m, v[maxn];

int i, saux, smax, step, ia, ib;

# define  min(x, y) ( (x)<(y) ? (x):(y) )
# define  max(x, y) ( (x)>(y) ? (x):(y) )

void update(int st, int dr, int n)
{
	if ( st==dr ) {
		d[n] = b[n] = c[n] = /*(v[st]<0 ? 0:v[st]),*/ a[n] = v[st];
	}
	
	else {
		int 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];
		// ...
	}
}

int qa[logn], qb[logn], qc[logn], qd[logn], sz;

void qrtree(int xa, int xb, int st, int dr, int n)
{
	if ( xa<=st && dr<=xb ) {
		qa[++sz]=a[n], qb[sz]=b[n], qc[sz]=c[n], qd[sz]=d[n];
	}
	
	else {
		int 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(int xa, int xb)
{
	sz=0, qrtree(xa, xb, 1, n, 1);
	
	saux = max(qa[1], qc[1]);
	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);
	}
}

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;
}