//subsecvente de suma maxima pe un anumit longrebal
//cu arbori de longrevale
#include <stdio.h>
#define lg_max 100010

using namespace std;

long A[lg_max*5],B[lg_max*5],C[lg_max*5],D[lg_max*5];

long n,m,sir[lg_max];
long St,Dr,Suma,Max;

inline long max(long a,long b)
{
     return a>b?a:b;
}

void baga(long nod,long st,long dr)
{
     if (st==dr)
     {
          A[nod]=B[nod]=C[nod]=D[nod]=sir[st];
          return ;
     }
     long mij=(st+dr)>>1;
     long L=(nod<<1);
     long R=(nod<<1)+1;
     baga(L,st,mij);
     baga(R,mij+1,dr);
     A[nod]=max(A[L],D[L]+A[R]);
     B[nod]=max(B[R],D[R]+B[L]);
     C[nod]=max(C[R],C[L]);
     C[nod]=max(C[nod],A[R]+B[L]);
     D[nod]=D[R]+D[L];
}

void cauta(long nod,long st,long dr)
{
     if (st>=St && Dr>=dr)
     {
          if (Suma<0)
               Suma=0;
          Max=max(Max,Suma+A[nod]);
          Max=max(Max,C[nod]);
          Suma=max(Suma+D[nod],B[nod]);
          return ;
     }
     long mij=(st+dr)>>1;
     long L=(nod<<1);
     long R=(nod<<1)+1;
     if (St<=mij)
          cauta(L,st,mij);
     if (Dr>=mij+1)
          cauta(R,mij+1,dr);

}

void citire()
{
     scanf ("%ld %ld\n",&n,&m);
     for (long i=1;i<=n;i++)
          scanf ("%ld ",&sir[i]);
     baga(1,1,n);
}

void solve()
{
     for (long i=0;i<m;i++)
     {
          scanf ("%ld %ld\n",&St,&Dr);
          Suma=0;
          Max=-200000;
          cauta(1,1,n);
          printf("%ld\n",Max);
     }
}

int main ()
{
     freopen ("sequencequery.in","r",stdin);
     freopen ("sequencequery.out","w",stdout);
     citire();
     solve();
     return 0;
}