#include<stdio.h>
#include<algorithm>
#define NMAX 100111
#define INF 1<<30
using namespace std;

struct sec {int tot,x,y,max;} sol,a[4*NMAX];
int m,i,n,n1,n2,x,y;


void update(int nod,int p,int u,int poz,int val){
int mij=(p+u)>>1;

  if(p == u){
  a[nod].tot=a[nod].x=a[nod].y=a[nod].max = val;
  return ;
  }

  if(poz <= mij) update(nod<<1,p,mij,poz,val);
  else           update((nod<<1)+1,mij+1,u,poz,val);

n1=nod<<1;
n2=(nod<<1)+1;

  a[nod].tot=a[n1].tot+a[n2].tot;
  a[nod].max=max(a[n1].max, a[n2].max);
  a[nod].max=max(a[nod].max, a[n1].y + a[n2].x);
  a[nod].y=max(a[n2].y, a[n2].tot + a[n1].y);
  a[nod].x=max(a[n1].x, a[n1].tot + a[n2].x);

}

int query(int nod,int p,int u,int A,int B){
int mij=(p+u)>>1;

   if(A<=p && u<=B){
    if(sol.tot == -INF) sol.tot=a[nod].tot;
    else sol.tot+= a[nod].tot;
   sol.max = max(sol.max,a[nod].max);
   sol.max = max(sol.max,sol.y+a[nod].x);
   sol.y = max(a[nod].y, a[nod].tot + sol.y);
   return 0;
   }

   if(A<=mij) query(nod<<1,p,mij,A,B);
   if(B>mij)  query((nod<<1)+1,mij+1,u,A,B);

}


int main(){

FILE *f=fopen("sequencequery.in","r");
FILE *g=fopen("sequencequery.out","w");
fscanf(f,"%d %d",&n,&m);

  for(i=1;i<=4*n;i++)
  a[i].x=a[i].y=a[i].max=a[i].tot=-INF;

  for(i=1;i<=n;i++){
  fscanf(f,"%d",&x);
  update(1,1,n,i,x);
  }

  for(i=1;i<=m;i++){
  fscanf(f,"%d %d",&x,&y);
  sol.max=sol.x=sol.tot=sol.y=-INF;
  query(1,1,n,x,y);
  fprintf(g,"%d\n",sol.max);
  }

fclose(f);
fclose(g);

return 0;
}