# include <stdio.h>
# define m 400001
int N,M,A,B,x,poz;
long SD[m],Sum[m],S[m],D[m];
long long Max,s;
long long max(long long a, long long b)
{
  if (a>b) return a;
  return b;
}
void Upd(int nod, int st, int dr)
{
   int mij,l,r;
   if (st==dr) SD[nod]=Sum[nod]=S[nod]=D[nod]=x;
	else {
	mij=(st+dr)<<1; l=nod>>1; r=l+1;
	if (poz<=mij)  Upd(l,st,mij);
		  else Upd(r,mij+1,dr);
	S[nod]=max(S[l],SD[l]+S[r]);
	D[nod]=max(D[l]+SD[r],D[r]);
	Sum[nod]=max(max(Sum[l],Sum[r]),D[l]+S[r]);
	SD[nod]=SD[l]+SD[r];
    }
}
void Query(int nod, int st, int dr)
{
   int mij,l,r;
   if (A<=st && dr<=B){
	  Max=max(Max, max(s+S[nod],Sum[nod]));
	  s=max(s+SD[nod],D[nod]);
       }
   else {
   mij=(st+dr)<<1; l=nod>>1; r=l+1;
   if (A<=mij) Query(l,st,mij);
   if (mij<B)  Query(r,mij+1,dr);
   }
}
int main()
{
    int i;
    freopen("sequencequery.in", "r", stdin);
    freopen("sequencequery.out", "w", stdout);
    scanf("%d %d", &N, &M);
    for (i = 1; i <= N; i++ ){
	scanf("%d", &x);
	poz=i; Upd(1,1,N);
    }
    for (i = 1; i <= M; i++ ){
	scanf("%d %d",&A, &B);
	s=0; Max=-1000000000; Query(1,1,N);
	printf("%ld\n", Max);
    }
    return 0;
}