#include <fstream>
#include <algorithm>
#define INF 0x3f3f3f3f
#define NMAX (1<<18)
#define lf (nod<<1)
#define rt (lf+1)
#define mid ((left+right)>>1)
using namespace std;
ofstream out("sequencequery.out");
long long V[NMAX] , A[NMAX << 1] , B[NMAX << 1 ] , C[NMAX << 1 ] , arb[ NMAX << 1 ];
int n , m;
long long sum , sol;
void Read();
void build( int nod , int left , int right );
void query( int nod , int left , int right , int start , int finish);
int main()
{
Read();
return 0;
}
void Read()
{
ifstream in("sequencequery.in");
in >> n >> m;
for( int i=1 ; i<=n ; i++)
in >>V[i];
build( 1 , 1 , n );
for( int st , dr ; m ; --m )
{
in >> st >> dr ;
sum = 0 , sol = -INF;
query(1,1,n,st,dr);
out << sol << '\n';
}
}
void build( int nod , int left , int right )
{
if( left == right )
{
A[nod] = B[nod] = C[nod] = arb[nod] = V[left] ;
return;
}
//..
build( lf , left , mid);
build( rt , mid + 1 , right );
A[nod] = max( A[lf] , arb[lf] + A[rt] );
B[nod] = max( B[lf] + arb[rt] , B[rt] );
C[nod] = max( max( C[lf] , C[rt] ) , B[lf] + A[rt] );
arb[nod] = arb[lf] + arb[rt];
}
void query( int nod , int left , int right , int start , int finish )
{
if( start <= left && right <= finish )
{
sum = max( sum , 0LL );
sol = max( sol , max( sum + A[nod] , C[nod] ));
sum = max( sum + arb[nod] , B[nod] );
return;
}
if( start <= mid )
query( lf , left , mid , start , finish );
if( finish > mid )
query( rt , mid + 1 , right , start , finish );
}