#include <iostream>
#include <stdio.h>
#define NMAX 100000
using namespace std;
int v[NMAX];
struct arb {
int sum, spref, ssuf, smax;
} aint[2*NMAX];
inline int mid( int l, int r ) { return ( l + r ) / 2; }
inline int leftSon( int node ) { return node + 1; }
inline int rightSon( int node, int m, int l ) { return node + 2 * ( m - l + 1 ); }
arb attr( arb lson, arb rson ) {
arb x;
x.sum = lson.sum + rson.sum;
x.spref = max( lson.spref, lson.sum + rson.spref );
x.ssuf = max( rson.ssuf, rson.sum + lson.ssuf );
x.smax = max( x.sum, x.spref );
x.smax = max( x.smax, x.ssuf );
x.smax = max( x.smax, lson.smax );
x.smax = max( x.smax, rson.smax );
x.smax = max( x.smax, lson.ssuf + rson.spref );
return x;
}
void build( int node, int l, int r ) {
if( l == r ) {
aint[node].sum = aint[node].spref = aint[node].ssuf = aint[node].smax = v[l];
return;
}
int m = mid( l, r );
int lson = leftSon( node );
int rson = rightSon( node, m, l );
build( lson, l, m );
build( rson, m + 1, r );
aint[node] = attr( aint[lson], aint[rson] );
}
arb query( int node, int l, int r, int a, int b ) {
if( a <= l && r <= b ) {
return aint[node];
}
int m = mid( l, r );
int lson = leftSon( node );
int rson = rightSon( node, m, l );
if( b <= m )
return query( lson, l, m, a, b );
if( m < a )
return query( rson, m + 1, r, a, b );
arb left = query( lson, l, m, a, b );
arb right = query( rson, m + 1, r, a, b );
return attr( left, right );
}
int main() {
FILE *fin, *fout;
int n, m, i, x, y;
fin = fopen( "sequencequery.in", "r" );
fout = fopen( "sequencequery.out", "w" );
fscanf( fin, "%d%d", &n, &m );
for( i = 0; i < n; i++ )
fscanf( fin, "%d", &v[i] );
build( 0, 0, n - 1 );
for( ; m; m-- ) {
fscanf( fin, "%d%d", &x, &y );
fprintf( fout, "%d\n", query( 0, 0, n - 1, x - 1, y - 1 ).smax );
}
fclose( fin );
fclose( fout );
return 0;
}