#include<stdio.h>
#define Max 100000
#define max(a,b) ((a)>(b))? (a):(b)
#define min(a,b) ((a)<(b))? (a):(b)
#define ll long long
FILE*f=fopen("sequencequery.in","r");
FILE*g=fopen("sequencequery.out","w");
ll smax[3*Max+2], s[3*Max+2], sleft[3*Max+2], sright[3*Max+2];
ll a[Max+4],n,m;
ll sol,S;
void update(int node, int l, int r)
 {
 //if(l>r) return ;
 if(l==r)
   {
    s[node]=smax[node]=sright[node]=sleft[node]=a[r];
    return;
   }
 int m=(l+r)/2;
 update(2*node,l,m);
 update(2*node+1,m+1,r);
 int fs=2*node, fd=2*node+1;
 s[node]=s[fs]+s[fd];
 sleft[node]=max( sleft[fs], s[fs]+sleft[fd] );
 sright[node]=max ( sright[fd], s[fd] + sright[fs] );
 smax[node]=max(s[node], sleft[node]);
 smax[node]=max(smax[node], sright[node]);
 smax[node]=max(smax[node], smax[fs]);
 smax[node]=max(smax[node], smax[fd]);
 smax[node]=max(smax[node], sleft[fd]+sright[fs]);
 }
void query(int node, int l, int r, int i, int j)
 {
 if(l>r) return;
 if(i==l && j==r)
  {
  sol=max(sol, S+sleft[node]);
  S=max(S+s[node], sright[node]);
  sol=max(sol, smax[node]);
  sol=max(sol,S);
  return ;
  }
 int m=(r+l)/2;
 if(i<=m) query(2*node, l, m, i, min(j,m));
 if(j>m) query(2*node+1, m+1, r, max(i,m+1), j);
 }

int main()
 {
 fscanf(f,"%lld%lld",&n,&m);
 int i,x,y;
 for(i=1;i<=n;++i) fscanf(f,"%lld",&a[i]);
 update(1,1,n);
 while(m--)
  {
  fscanf(f,"%d%d",&x,&y);
  sol=S=-0x3f3f3f3f;
  query(1,1,n,x,y);
  fprintf(g,"%lld\n",sol);
  }
 return 0;
 }