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

using namespace std;

int A[lg_max*4],B[lg_max*4],C[lg_max*4],D[lg_max*4];

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

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

void baga(int nod,int st,int dr)
{
     if (st==dr)
     {
          A[nod]=B[nod]=C[nod]=D[nod]=sir[st];
          return ;
     }
     int mij=(st+dr)>>1;
     int L=(nod<<1);
     int 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(int nod,int st,int 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 ;
     }
     int mij=(st+dr)>>1;
     int L=(nod<<1);
     int R=(nod<<1)+1;
     if (St<=mij)
          cauta(L,st,mij);
     if (Dr>=mij+1)
          cauta(R,mij+1,dr);

}

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

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

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