#include <cstdio>
#include <algorithm>

#define LMAX 262144
#define NMAX 100000
#define ll long long

using namespace std;

int N, Q, i, x, Sir[NMAX], A, B;
ll ASt[LMAX], ADr[LMAX], AInt[LMAX], AFull[LMAX], Rez, Sum;

inline void Build( int Nod, int St, int Dr )
{
	if( St == Dr )
	{
		ASt[ Nod ] = ADr[ Nod ] = AInt[ Nod ] = AFull[ Nod ] = Sir[ St ];
		return;
	}
	
	int M = St + ((Dr - St)>>1);
	
	Build( (Nod<<1), St, M );
	Build( ((Nod<<1)|1), M + 1, Dr );
	
	AFull[ Nod ] = AFull[ (Nod<<1) ] + AFull[ ((Nod<<1)|1) ];
	
	ASt[ Nod ] = max( ASt[ (Nod<<1) ], AFull[ (Nod<<1) ] );
	ASt[ Nod ] = max( ASt[ Nod ], AFull[ (Nod<<1) ] + ASt[ ((Nod<<1)|1) ] );
	
	ADr[ Nod ] = max( ADr[ ((Nod<<1)|1) ], AFull[ ((Nod<<1)|1) ] );
	ADr[ Nod ] = max( ADr[ Nod ], AFull[ ((Nod<<1)|1) ] + ADr[ (Nod<<1) ] );
	
	AInt[ Nod ] = max( AInt[ (Nod<<1) ], AInt[ ((Nod<<1)|1) ] );
	AInt[ Nod ] = max( AInt[ Nod ], ADr[ (Nod<<1) ] + ASt[ ((Nod<<1)|1) ] );
}

inline void Query( int Nod, int St, int Dr )
{
	if( A <= St && Dr <= B )
	{
		Rez = max( Rez, max( Sum + ASt[ Nod ], AInt[ Nod ] ) );
		Sum = max( Sum + AFull[ Nod ], ADr[ Nod ] );
		
		return;
	}
	
	int M = St + ((Dr - St)>>1);
	
	if( A <= M ) Query( (Nod<<1), St, M );
	if( B > M ) Query( ((Nod<<1)|1), M + 1, Dr );
}

int main()
{
	freopen("sequencequery.in", "r", stdin);
	freopen("sequencequery.out", "w", stdout);
	
	scanf("%d%d", &N, &Q );
	for( i = 1; i <= N; ++i )
		scanf("%d", &Sir[i] );
	
	Build( 1, 1, N );
	
	for( ; Q--; )
	{
		scanf("%d%d", &A, &B );
		Rez = -(1LL<<60), Sum = 0;
		Query( 1, 1, N );
		printf("%lld\n", Rez);
	}
	
	return 0;
}