#include <stdio.h>
#include <algorithm>
#define NMax 100010
using namespace std;
typedef long long ll;
const char IN[]="sequencequery.in",OUT[]="sequencequery.out";
const ll INF= 100000000000000LL;
int N,M;
int a[NMax];
ll A[4*NMax] , B[4*NMax] , C[4*NMax] , Sum[4*NMax] , ret , S;
void make(int poz,int st,int dr)
{
if (st==dr){
A[poz]=B[poz]=C[poz]=Sum[poz]=a[st];
return;
}
int m=(st+dr)>>1;
make( 2*poz , st , m );
make( 2*poz+1, m+1, dr);
A[poz]= max( A[2*poz] , Sum[2*poz]+A[2*poz+1] );
B[poz]= max( B[2*poz+1], B[2*poz]+Sum[2*poz+1] );
C[poz]= max( max ( C[2*poz] , C[2*poz+1] ) , B[2*poz]+A[2*poz+1]);
Sum[poz]= Sum[2*poz]+Sum[2*poz+1];
}
void Query(int poz,int st,int dr,int x,int y)
{
if ( x<=st && dr<=y )
{
ret= max ( ret , max( S+A[poz] , C[poz] ));
S= max( S+Sum[poz] , B[poz] );
return;
}
int m=(st+dr)>>1;
if ( x<=m ) Query(2*poz , st , m , x , y );
if ( y >m ) Query(2*poz+1, m+1, dr, x , y );
}
int main()
{
int i,x,y;
freopen(IN,"r",stdin);
scanf("%d%d",&N,&M);
for (i=0;i<N;++i) scanf("%d",a+i);
make(1,0,N-1);
freopen(OUT,"w",stdout);
while (M--)
{
scanf("%d%d",&x,&y);--x;--y;
ret=-INF;S=0;
Query(1,0,N-1,x,y);
printf("%lld\n",ret);
}
fclose(stdout);
fclose(stdin);
return 0;
}