#include<bits/stdc++.h>
using namespace std;
struct ajutornod{
  long long st,dr,mij;
  long long sum;
};
const int N=200005;
ajutornod aint[4*N];
int v[N];
void mrge(int nod){
  ajutornod fiust=aint[2*nod];
  ajutornod fiudr=aint[2*nod+1];
  ajutornod &x=aint[nod];

  x.st=max(fiust.st,fiust.sum+fiudr.st);
  x.dr=max(fiudr.dr,fiudr.sum+fiust.dr);
  x.sum=fiust.sum+fiudr.sum;
  x.mij=max(max(fiust.mij,fiudr.mij),fiust.dr+fiudr.st);
}
const long long INF=1LL<<40;
void build(int nod,int st,int dr){
  if(st>dr)
    return;
  if(st==dr){
    aint[nod]={v[st],v[st],v[st],v[st]};
    return;
  }
  int mid=(st+dr)/2;
  build(2*nod,st,mid);
  build(2*nod+1,mid+1,dr);
  mrge(nod);
}

void update(int nod,int st,int dr,int upoz,int val){
  if(st>dr || upoz<st || upoz>dr){
    return;
  }
  if(st==dr){
    aint[nod]={val,val,val,val};
    return;
  }
  int mid=(st+dr)/2;
  update(2*nod,st,mid,upoz,val);
  update(2*nod+1,mid+1,dr,upoz,val);
  mrge(nod);
}
void query(int nod,int st,int dr,int qst,int qdr,ajutornod &rasp){
  if(st>dr || qdr<st || qst>dr){
    return;
  }
  if(qst<=st && dr<=qdr){
    rasp.mij=max(max(rasp.mij,aint[nod].mij),rasp.dr+aint[nod].st);
    rasp.dr=max(aint[nod].dr,aint[nod].sum+rasp.dr);
    return;
  }
  int mid=(st+dr)/2;
  query(2*nod,st,mid,qst,qdr,rasp);
  query(2*nod+1,mid+1,dr,qst,qdr,rasp);
}
int main()
{
  FILE*fin,*fout;
  fin=fopen("sequencequery.in","r");
  fout=fopen("sequencequery.out","w");
  int n,q;
  fscanf(fin,"%d%d",&n,&q);
  for(int i=1;i<=n;i++){
    fscanf(fin,"%d",&v[i]);
  }
  build(1,1,n);
  for(int i=1;i<=q;i++){
    int a,b;
    fscanf(fin,"%d%d",&a,&b);
    ajutornod rasp={-INF,-INF,-INF,-INF};
    query(1,1,n,a,b,rasp);
    fprintf(fout,"%lld\n",rasp.mij);
  }
  return 0;
}