#include <bits/stdc++.h>
using namespace std;
ifstream fin ("sequencequery.in");
ofstream fout ("sequencequery.out");
int n, m;
const int INF = 1e9;
struct Nod{
int sum, psum, ssum, ssmax;
};
Nod arbi[400005];
Nod nodupdate(Nod st, Nod dr)
{
Nod ans;
ans.sum=st.sum+dr.sum;
ans.psum=max(st.psum, st.sum+dr.psum);
ans.ssum=max(dr.ssum, dr.sum+st.ssum);
ans.ssmax=max(max(st.ssmax, dr.ssmax), st.ssum+dr.psum);
return ans;
}
void update(int nod, int st, int dr, int val, int pozi)
{
if(st==dr)
{
arbi[nod]={val, val, val, val};
return;
}
int mij=(st+dr)/2;
if(pozi<=mij)
update(nod*2, st, mij, val, pozi);
else
update(nod*2+1, mij+1, dr, val, pozi);
arbi[nod]=nodupdate(arbi[nod*2], arbi[nod*2+1]);
return;
}
Nod query(int nod, int st, int dr, int qst, int qdr)
{
if(qst<=st && dr<=qdr)
return arbi[nod];
if(qdr<st || dr<qst)
{
Nod aux={-INF, -INF, -INF, -INF};
return aux;
}
int mij=(st+dr)/2;
return nodupdate(query(nod*2, st, mij, qst, qdr),query(nod*2+1, mij+1, dr, qst, qdr));
}
void citti()
{
fin>>n>>m;
int x;
for(int i=1; i<=n; i++)
{
fin>>x;
update(1, 1, n, x, i);
}
}
void rezi()
{
int c,p;
for(int i=1; i<=m; i++)
{
fin>>c>>p;
fout<<query(1, 1, n, c, p).ssmax<<'\n';
}
}
int main()
{
citti();
rezi();
return 0;
}