#include<cstdio>
#include<fstream>

using namespace std;

const int MaxArb = 1 << 18;
const long long INF = 2147000000;

#define max(a, b) ((a)>(b)?(a):(b))

struct arbore{
		long long s,d,t,m;
		} A[MaxArb];
int n,q,val,poz,st,dr;
long long sol,s;

void update( int nod , int left , int right )
{
	if( left == right )
		{
			A[nod].s = A[nod].d = A[nod].t = A[nod].m = val;
			return ;
		}
	int midd = (left + right ) >> 1;
	if( poz <= midd )
		update( 2*nod , left , midd );
		else
		update( 2*nod+1 , midd+1 , right );
	A[nod].t = A[2*nod].t + A[2*nod+1].t;
	A[nod].s = max( A[2*nod].t + A[2*nod+1].s , A[2*nod].s );
	A[nod].d = max ( A[2*nod+1].t + A[2*nod].d , A[2*nod+1].d );
	A[nod].m = max ( max( A[2*nod].m , A[2*nod+1].m ) , A[2*nod].d + A[2*nod+1].s );
}

void query( int nod , int left , int right )
{
	if( st <= left && right <= dr )
		{
			sol = max( sol , max ( s+ A[nod].s ,A[nod].m) );
			s = max ( s+ A[nod].t , A[nod].d );
			return ;
		}
	int midd = ( left + right ) >> 1;
	if( st <= midd )
		query( 2*nod , left , midd );
	if( midd < dr )
		query( 2*nod+1 , midd+1 , right );
}

int main()
{
	freopen( "sequencequery.in" , "r" , stdin );
	freopen( "sequencequery.out" , "w" , stdout );
	int i;
	scanf("%d %d" , &n , &q );
	for( i = 1 ; i <= n ; i++ )
		{
			scanf("%d" , &val);
			poz = i;
			update(1,1,n);
		}
	for( i = 1 ; i <= q ; i++ )
		{
			scanf("%d%d" , &st , &dr );
			s = 0;
			sol = -INF;
			query(1,1,n);
			printf("%lld\n" , sol );
		}
	return 0;
}