#include <stdio.h>

#define infile "sequencequery.in"
#define outfile "sequencequery.out"
#define NMAX 100005
struct NOD {int li,ls; long long suma,sumamax,sumabegin,sumaend; NOD *st,*dr;};
FILE *fin,*fout;
NOD *prim;
int n,v[NMAX];

inline long long max(long long x, long long y)
  {
   return (x>y)?x:y;
  }

void creare_arbore(NOD *(&prim), int li, int ls)
  {
   prim=new NOD;
   prim->st=NULL;
   prim->dr=NULL;
   prim->li=li;
   prim->ls=ls;

   if(li==ls)
     prim->suma=prim->sumamax=prim->sumabegin=prim->sumaend=v[li];
   else
    {
     creare_arbore(prim->st,li,(li+ls)/2);
     creare_arbore(prim->dr,(li+ls)/2+1,ls);
     prim->suma=prim->st->suma+prim->dr->suma;
     prim->sumabegin=max(prim->st->sumabegin,prim->st->suma+prim->dr->sumabegin);
     prim->sumaend=max(prim->dr->sumaend,prim->dr->suma+prim->st->sumaend);
     prim->sumamax=max(prim->st->sumamax,prim->dr->sumamax);
     prim->sumamax=max(prim->sumamax,prim->st->sumaend+prim->dr->sumabegin);
    }
  }

int interogare(NOD *(&prim), int li, int ls, int start, int end, long long &suma, long long &sumamax, long long &sumabegin, long long &sumaend)
  {
   if(start<=li && end>=ls)
     {suma=prim->suma;
      sumamax=prim->sumamax;
      sumabegin=prim->sumabegin;
      sumaend=prim->sumaend;
      return 1;}
   else
     {
      int mij=(li+ls)/2;
      long long suma1,sumamax1,sumabegin1,sumaend1,suma2,sumamax2,sumabegin2,sumaend2;
      int answer1=0,answer2=0;
      if(start<=mij)
        answer1=interogare(prim->st,li,mij,start,end,suma1,sumamax1,sumabegin1,sumaend1);
      if(end>mij)
        answer2=interogare(prim->dr,mij+1,ls,start,end,suma2,sumamax2,sumabegin2,sumaend2);
      if(answer1)
        if(answer2)
          {
           suma=suma1+suma2;
           sumabegin=max(sumabegin1,suma1+sumabegin2);
           sumaend=max(sumaend2,suma2+sumaend1);
           sumamax=max(sumamax1,sumamax2);
           sumamax=max(sumamax,sumaend1+sumabegin2);
           return 1;
          }
        else
          {
           suma=suma1;
           sumamax=sumamax1;
           sumabegin=sumabegin1;
           sumaend=sumaend1;
           return 1;
          }
      else
        if(answer2)
          {
           suma=suma2;
           sumamax=sumamax2;
           sumabegin=sumabegin2;
           sumaend=sumaend2;
           return 1;
          }
        else
          return 0;
     }
  }


int main()
{
int i,k,start,end;
long long suma,sumamax,sumabegin,sumaend;
fin=fopen(infile,"r");
fout=fopen(outfile,"w");
fscanf(fin,"%d %d",&n,&k);
for(i=0;i<n;i++)
   fscanf(fin,"%d",&v[i]);
prim=NULL;
creare_arbore(prim,0,n-1);
for(i=0;i<k;i++)
  {
   fscanf(fin,"%d %d",&start,&end);
   interogare(prim,0,n-1,start-1,end-1,suma,sumamax,sumabegin,sumaend);
   fprintf(fout,"%Ld\n",sumamax);
  }
fclose(fin);fclose(fout);
return 0;
}