#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
long long v[100005],sp[100005],maxi[505],mini[505],sub[505];
long long group(long long k,long long x){
long long nr=x/k+1;
if (x%k==0)
nr--;
return nr;}
int main(){
freopen("sequencequery.in","r",stdin);
freopen("sequencequery.out","w",stdout);
long long n,m,i,k,cnt=0,j,x,y,gx,gy,rasp,minim;
scanf("%lld%lld",&n,&m);
k=(long long)sqrt((double)n);
for(i=1;i<=n;i++)
scanf("%lld",&v[i]),sp[i]=sp[i-1]+v[i];
for(i=0;i<=500;i++)
mini[i]=20000000000,maxi[i]=-20000000000,sub[i]=-20000000000;
for(i=1;i<=n;i=i+k){
cnt++;
for(j=i;j<=n && j<i+k;j++)
maxi[cnt]=max(maxi[cnt],sp[j]),mini[cnt]=min(mini[cnt],sp[j]);
minim=sp[i-1];
for(j=i;j<=n && j<i+k;j++){
if (sub[cnt]<sp[j]-minim)
sub[cnt]=sp[j]-minim;
if (minim>sp[j])
minim=sp[j];}}
for(i=1;i<=m;i++){
scanf("%lld%lld",&x,&y);
gx=group(k,x);
gy=group(k,y);
rasp=-20000000000;
if (gx==gy){
minim=sp[x-1];
for(j=x;j<=y;j++){
if (rasp<sp[j]-minim)
rasp=sp[j]-minim;
if (sp[j]<minim)
minim=sp[j];}
printf("%lld\n",rasp);}
else{
minim=sp[x-1];
for(j=x;j<=gx*k;j++){
if (rasp<sp[j]-minim)
rasp=sp[j]-minim;
if (sp[j]<minim)
minim=sp[j];}
for(j=gx+1;j<gy;j++){
if (rasp<maxi[j]-minim)
rasp=maxi[j]-minim;
if (rasp<sub[j])
rasp=sub[j];
if (mini[j]<minim)
minim=mini[j];}
for(j=(gy-1)*k+1;j<=y;j++){
if (rasp<sp[j]-minim)
rasp=sp[j]-minim;
if (sp[j]<minim)
minim=sp[j];}
printf("%lld\n",rasp);}}
return 0;}