#include<cstdio>
#include<iostream>
#define nmax 100010
using namespace std;
int nr[nmax],n,m,s1,s2;
long long secv[4*nmax+66];
int strt[4*nmax+66],stp[4*nmax+66];
long long maxi(long long a,long long b,long long c)
{
int mx=a;
if(mx<b) mx=b;
if(mx<c) mx=c;
return mx;
}
int build(int poz,int st,int dr)
{
int i,loc=(st+dr)/2;
long long num;
if(st==dr)
{
secv[poz]=nr[st];
strt[poz]=st;
stp[poz]=dr;
return 1;
}
build(2*poz,st,loc);
build(2*poz+1,loc+1,dr);
num=secv[2*poz]+secv[2*poz+1];
for(i=stp[2*poz]+1;i<strt[2*poz+1];i++) num+=nr[i];
secv[poz]=maxi(secv[2*poz],secv[2*poz+1],num);
if(secv[poz]==secv[2*poz]) { strt[poz]=strt[2*poz]; stp[poz]=stp[2*poz]; return 1; }
if(secv[poz]==secv[2*poz+1]) { strt[poz]=strt[2*poz+1]; stp[poz]=stp[2*poz+1]; return 1; }
if(secv[poz]==num) { strt[poz]=strt[2*poz]; stp[poz]=stp[2*poz+1]; return 1; }
}
long long query(int poz,int str,int stop,int st,int dr)
{
int i,loc=(st+dr)/2,l1=0,l2=0,l3=0,l4=0;
long long p1=0,p2=0,p3=0;
long long num;
//cout<<poz<<' '<<str<<' '<<stop<<' '<<st<<' '<<dr<<' '<<loc<<'\n';;
if(str==st && stop==dr)
{
s1=strt[poz]; s2=stp[poz]; return secv[poz];
}
if(str<=loc)
{
if(stop>loc) p1=query(2*poz,str,loc,st,loc);
else p1=query(2*poz,str,stop,st,loc);
l1=s1; l2=s2;
}
if(stop>loc)
{
if(str<=loc) p2=query(2*poz+1,loc+1,stop,loc+1,dr);
else p2=query(2*poz+1,str,stop,loc+1,dr);
l3=s1; l4=s2;
}
if(p1==0) { p3=p2; s1=l3; s2=l4; return p3; }
else if(p2==0) { p3=p1; s1=l1; s2=l2; return p3; }
else
{
num=p1+p2;
for(i=l2+1;i<l3;i++) num+=nr[i];
p3=maxi(p1,p2,num);
if(p3==p1) { s1=l1; s2=l2; return p3; }
if(p3==p2) { s1=l3; s2=l4; return p3; }
if(p3==num) { s1=l1; s2=l4; return p3; }
}
//if(poz==2) { for(i=l2+1;i<l3;i++) cout<<"fa"<<i<<' '<<nr[i]<<'\n';
// cout<<l1<<' '<<l2<<' '<<l3<<' '<<l4<<' '<<poz<<" "<<p1<<' '<<p2<<' '<<p3<<' '<<num<<'\n';;}
}
int main()
{
int i,j,n1,n2;
freopen("sequencequery.in","r",stdin);
freopen("sequencequery.out","w",stdout);
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++) { scanf("%d",&nr[i]);}
build(1,1,n);
//cout<<query(1,6,6,1,n);
for(i=1;i<=m;i++)
{
scanf("%d%d",&n1,&n2);
if(n1<1) n1=1;
printf("%ld\n",query(1,n1,n2,1,n));
}
fclose(stdin);
fclose(stdout);
return 0;
}