#include<stdio.h>
#define Nmax 100010
#define Inf 1<<30

#define st (1<<nod)
#define dr 1 + (1<<nod)

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

struct arb { int x,s,d,sum; } A[Nmax<<2];

int i,n,m,a,b,x,Sum;

void update( int nod, int s, int d )
{
	if ( a <= s && d <= b )
	{
		A[nod].x = A[nod].s = A[nod].d = A[nod].sum = x ;
		return ; 
	}
	
	int m = (s+d) >> 1 ;
	
	if( a <= m ) update(st,s,m);
	if( m < b  ) update(dr,m+1,d);
	
	A[nod].x = Max ( Max ( A[st].x , A[dr].x ) , A[st].d + A[dr].s ) ; 
	A[nod].sum = A[st].sum + A[dr].sum ;
	
	A[nod].s = Max ( A[st].s , A[st].sum + A[dr].s ) ;
	A[nod].d = Max ( A[dr].d , A[dr].sum + A[st].d ) ;
}

void query ( int nod , int s, int d )
{
	int rez ; 
	
	if ( a <= s && d <= b ) 
	{
		rez = A[nod].x  ;
		
		if( Sum + A[nod].s > rez ) 	rez = Sum + A[nod].s;
		
		if( Sum + A[nod].sum > A[nod].d ) Sum += A[nod].sum ;
			else						   Sum = A[nod].d ;
		
		if( rez > x ) 
			x = rez ;
		
		return ;
	}
	
	int m = (s+d) >> 1 ;
	
	if( a <= m ) query(st,s,m);
	if( m < b  ) query(dr,m+1,d);
}


int main()
{
	freopen("sequencequery.in","r",stdin);
	freopen("sequencequery.out","w",stdout);
	
	scanf("%d %d",&n,&m);
	
	for( i = 1 ; i <= n ; i++ )
	{
		scanf("%d",&x);
		a = b = i ;
		update(1,1,n);
	}
	
	for( i = 1 ; i <= m ; i++ )
	{
		scanf("%d %d",&a,&b);
		
		x = - Inf ; Sum = 0 ;
		query(1,1,n);
		
		printf("%d\n",x);
	}
	
	return 0;
}