#include<stdio.h>
#define Max 100000
#define max(a,b) ((a)>(b))? (a):(b)
FILE*f=fopen("sequencequery.in","r");
FILE*g=fopen("sequencequery.out","w");
int smax[3*Max+2], s[3*Max+2], sleft[3*Max+2], sright[3*Max+2];
int a[Max],n,m, v[Max], vf;
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(i<=l && r<=j)
  {
  v[++vf]=node;
  return;
  }
 int m=(r+l)/2;
 if(i<=m) query(2*node, l, m, i, j);
 if(j>m) query(2*node+1, m+1, r, i, j);
 }
int suma()
 {
 int i, sum;
 sum=smax[v[1]];
 for(i=2;i<=vf; ++i)
  {
  sum=max(smax[v[i-1]], smax[v[i]]);
  sum=max(sum, sleft[v[i]]+sright[v[i-1]]);
  sum=max(sum, s[v[i]]+s[v[i-1]]);
  sum=max(sum, s[v[i-1]] + sleft[v[i]]);
  sum=max(sum, sright[v[i-1]]+s[v[i]] );
  }
 return sum;
 }

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