# include <stdio.h>
# define m 101
/*
  SD[] suma tuturor elem din st - dr
  S[] suma maxima din stanga
  D[] suma maxima din dreapta
  Sum[] suma secventei maxime
 */
int N,M,A,B,x,poz;
long SD[m],Sum[m],S[m],D[m],Max,s;
long max(long a, 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)/2; l=2*nod; 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){
	  //if (s<0) s=0;
	  Max=max(Max, max(s+S[nod],Sum[nod]));
	  s=max(s+SD[nod],D[nod]);
       }
   else {
   mij=(st+dr)/2; l=2*nod; 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;
}