#include<fstream.h>
#define nx 500000
typedef long long ll;
ll A[nx],B[nx],C[nx],S[nx];
ll BAL,JOBB,s,Max,poz,what;

inline ll max(ll a,ll b)
 {
  if (a>b) return a;
  return b;
 }

void update (int nod,int st,int dr)
 {
  if (st==dr)
   {
    A[nod]=B[nod]=C[nod]=S[nod]=what;
    return;
   }
  int mij=(st+dr)/2,f=nod*2;
  int r=f+1;
  if (poz<=mij)
    update (f,st,mij);
  else
    update (r,mij+1,dr);
  A[nod]=max(A[f],S[f]+A[r]);
  B[nod]=max(B[r],B[f]+S[r]);
  C[nod]=max(max(C[f],C[r]),A[r]+B[f]);
  S[nod]=S[f]+S[r];
 }

void query (int nod,int st,int dr)                   
 {
  if (BAL<=st && dr<=JOBB)
   {
    Max=max(Max,max(s+A[nod],C[nod]));
    s=max(s+S[nod],B[nod]);
   }
  else
  {
  int mij=(st+dr)/2;
  if (BAL<=mij)
    query(nod*2,st,mij);
  if (JOBB>mij)
    query(nod*2+1,mij+1,dr);
  }
 }

int main()
 {
  ifstream be ("sequencequery.in");
  ofstream ki ("sequencequery.out");
  int i,n,t;
  be>>n>>t;
  for (i=1;i<=n;++i)
   {
    be>>what;
    poz=i;
    update(1,1,n);
   }
  for (;t;--t)
   {
    be>>BAL>>JOBB;
    s=0;
    Max=-(1<<61);
    query(1,1,n);
    ki<<Max<<'\n';
   }
  be.close();
  ki.close();
  return 0;
 }