#include<cstdio>
#include<algorithm>
using namespace std;
const int NMAX = 100005;
const int LMAX = (1<<18)+5;
int N,Q,i,V[NMAX],X,Y;
long long A[LMAX],B[LMAX],C[LMAX],S[LMAX],Sol,Sum;
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=1LL<<63; Query(1,1,N);
	    printf("%lld\n",Sol);
	}
	return 0;
}