#include <algorithm>
#include <cstdio>
using namespace std;
int const maxn=100*1000,maxt=(4*maxn-1),
cnst=5,log_maxn=20,maxr=cnst*log_maxn;
typedef long long int lli;
struct tree
{
int A[maxn],N;
// when x represents the interval [i..j],
// x.b = max { A[s]+...+A[t], i<=s<=t<=j },
// x.p = max { A[i]+...+A[s], i<=s<=j },
// x.s = max { A[t]+...+A[j], i<=t<=j }, and
// x.t = A[i]+...A[j].
struct segment{lli b,p,s,t;};
segment T[maxt];
int inline c0(int n){return 2*(n+1)-1;}
int inline c1(int n){return 2*(n+1);}
int inline m0(int a,int b){return (a+b)/2;}
int inline m1(int a,int b){return (a+b)/2+1;}
void init(int n,int a,int b)
{ if(a==b)
{T[n].b=T[n].p=T[n].s=T[n].t=A[a];return;}
init(c0(n),a,m0(a,b));
init(c1(n),m1(a,b),b);
int n0=c0(n),n1=c1(n);
T[n].b=max(T[n0].b,max(T[n1].b,T[n0].s+T[n1].p));
T[n].p=max(T[n0].p,T[n0].t+T[n1].p);
T[n].s=max(T[n1].s,T[n1].t+T[n0].s);
T[n].t=T[n0].t+T[n1].t;
}
void init(){init(0,0,N);}
int X,Y,L,R[maxr];
void traversal(int n,int a,int b)
{ if((X<=a)&&(b<=Y))
{R[L++]=n;return;}
if(X<=m0(a,b)){traversal(c0(n),a,m0(a,b));}
if(m1(a,b)<=Y){traversal(c1(n),m1(a,b),b);}
}
void buildRXY(int x,int y)
{X=x;Y=y;L=0;traversal(0,0,N);}
lli query(int x,int y)
{ buildRXY(x,y);
// case 1:
lli b=T[R[0]].b;int i;
for(i=1;L>i;++i)
{if(T[R[i]].b>b){b=T[R[i]].b;}}
// case 2:
lli v=T[R[0]].s,b1;
for(i=1;L>i;++i)
{ b1=v+T[R[i]].p;
if(b<b1){b=b1;}
v=max(v+T[R[i]].t,T[R[i]].s);
}
return b;
}
};
tree T;
int main()
{ freopen("sequencequery.in","r",stdin);
freopen("sequencequery.out","w",stdout);
int n,m,i,x,y;lli q;
scanf("%d %d",&n,&m);
for(i=0;n>i;++i){scanf("%d",T.A+i);}
T.N=n-1;T.init();
for(i=0;m>i;++i)
{ scanf("%d %d",&x,&y);--x;--y;
q=T.query(x,y);
printf("%lld\n",q);
}
return 0;
}