#include<cstdio>
#define inf 9999999999
using namespace std;

int N,M,X,Y,i,val,rez,a[100002];
long long sum,best;
struct leaf {long tot; long mxm; long st; long dr;};
leaf v[400002];

long long maximum(long a, long b)
{if(a>b)
   return a;
 return b;}

void query(int nod, int left, int right)
{if(X<=left && right<=Y)
   {if(best<maximum(v[nod].mxm,sum+v[nod].st))
      best=maximum(v[nod].mxm,sum+v[nod].st); 
    if(sum+v[nod].tot>v[nod].dr)
      sum=sum+v[nod].tot;
    else
      sum=v[nod].dr;
    return;}  
 int mid=(left+right)/2;
 if(X<=mid)
    query(2*nod,left,mid);
 if(Y>mid)  
    query(2*nod+1,mid+1,right); 
} 

void build(int nod, int left, int right)
{if(left==right)
  {v[nod].mxm=v[nod].tot=v[nod].st=v[nod].dr=a[left];
   return;}
 int mid=(left+right)/2;
 
 build(2*nod,left,mid); 
 build(2*nod+1,mid+1,right); 
 
 v[nod].tot=v[2*nod].tot+v[2*nod+1].tot;
 v[nod].mxm=maximum(v[2*nod].mxm,v[2*nod+1].mxm);
 v[nod].mxm=maximum(v[nod].mxm,(v[2*nod].dr+v[2*nod+1].st));
 v[nod].st=maximum((v[2*nod].tot+v[2*nod+1].st),v[2*nod].st);
 v[nod].dr=maximum((v[2*nod+1].tot+v[2*nod].dr),v[2*nod+1].dr);

}

int main()
{freopen("sequencequery.in","r",stdin);
freopen("sequencequery.out","w",stdout);
scanf("%d %d",&N,&M);
for(i=1; i<=N; i++)
  scanf("%d",&a[i]);
build(1,1,N);
 
  
for(i=1; i<=M; i++)  
  {scanf("%d %d",&X,&Y);
   sum=-inf;  best=-inf;
   query(1,1,N);
   printf("%d\n",best);}


return 0;}