#include <bits/stdc++.h>
using namespace std;
ifstream fin ("sequencequery.in");
ofstream fout ("sequencequery.out");
const int MAXN=100010;
struct nod{
long long r,p,s,sum;
}aint[4*MAXN];
int n,q;
void Update (int val, int pos, int l, int r, int node){
if (l==r){
aint[node].p=aint[node].s=aint[node].r=aint[node].sum=val;
return;
}
int mij=(l+r)/2;
if (mij<pos)
Update (val,pos,mij+1,r,2*node+1);
else
Update (val,pos,l,mij,2*node);
aint[node].sum=aint[2*node].sum+aint[2*node+1].sum;
aint[node].p=max (aint[2*node].p, aint[2*node].sum+aint[2*node+1].p);
aint[node].s=max (aint[2*node+1].s, aint[2*node+1].sum+aint[2*node].s);
aint[node].r=max ({aint[2*node].r,aint[2*node+1].r,aint[2*node].s+aint[2*node+1].p});
}
nod Query (int node, int ql, int qr, int l, int r){
if (l>qr || r<ql || l>r){
nod stop;
stop.p=stop.s=stop.r=-1e9;
stop.sum=0;
//fout <<stop.sum<<' ';
return stop;
}
if (ql<=l && r<=qr)
return aint[node];
int mij=(l+r)/2;
nod rez1=Query (2*node,ql,qr,l,mij);
nod rez2=Query (2*node+1,ql,qr,mij+1,r);
nod x;
x.r=max ({rez1.r,rez2.r,rez1.s+rez2.p});
x.p=max ({rez1.p,rez1.sum+rez2.p});
x.s=max ({rez2.s,rez2.sum+rez1.s});
x.sum=rez1.sum+rez2.sum;
return x;
}
int main()
{
fin >>n>>q;
for (int i=0;i<MAXN;++i){
aint[i].s=aint[i].p=aint[i].r=-1e9;
}
for (int i=1;i<=n;++i){
int x;
fin >>x;
Update (x,i,1,n,1);
//fout <<aint[1].r<<' ';
}
for (int i=1;i<=q;++i){
int a,b;
fin >>a>>b;
nod rez=Query (1,a,b,1,n);
fout <<rez.r<<'\n';
}
fin.close ();
fout.close ();
return 0;
}