#include<cstdio>
#include<algorithm>
using namespace std;
const int NMAX = 100005;
const int LMAX = (1<<18)+5;
int N,Q,i,V[NMAX],A[LMAX],B[LMAX],C[LMAX],S[LMAX],Sol,Sum,X,Y;
void Build(int Node,int L,int R)
{
if(L==R) {A[Node]=B[Node]=C[Node]=S[Node]=V[L]; return;}
int M=(L+R)/2; int LS=2*Node; int RS=LS+1;
Build(LS,L,M); Build(RS,M+1,R);
A[Node]=max(A[LS],S[LS]+A[RS]);
B[Node]=max(B[RS],S[RS]+B[LS]);
C[Node]=max(max(C[LS],C[RS]),B[LS]+A[RS]);
S[Node]=S[LS]+S[RS];
}
void Query(int Node,int L,int R)
{
if(L>=X && R<=Y)
{
if(Sum<0) Sum=0;
Sol=max(Sol,max(Sum+A[Node],C[Node]));
Sum=max(Sum+S[Node],B[Node]);
return;
}
int M=(L+R)/2; int LS=2*Node; int RS=LS+1;
if(X<=M) Query(LS,L,M);
if(Y>M) Query(RS,M+1,R);
}
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",&V[i]);
Build(1,1,N);
for(;Q;Q--)
{
scanf("%d%d",&X,&Y);
Sum=0; Sol=1<<31; Query(1,1,N);
printf("%d\n",Sol);
}
return 0;
}