#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("sequencequery.in");
ofstream fout("sequencequery.out");
int y[100001];
struct D{
long long int s, r, pref, suf;
}x[400001];
D C(D a, D b)
{D c;
c.s=a.s+b.s;
c.pref=max(a.pref, a.s+b.pref);
c.suf=max(b.suf, b.s+a.suf);
c.r=max(a.suf+b.pref, max(a.r, b.r));
return c;
}
void Build(int nod, int st, int dr)
{if(st==dr)
x[nod].r=x[nod].s=x[nod].pref=x[nod].suf=y[st];
else
{int mij=(st+dr)/2;
Build(nod*2, st, mij);
Build(nod*2+1, mij+1, dr);
x[nod]=C(x[nod*2], x[nod*2+1]);
}
}
D Query(int nod, int st, int dr, int qs, int qd)
{if(st>=qs && dr<=qd)
return x[nod];
else
{int mij=(st+dr)/2;
if(mij>=qd)return Query(nod*2, st, mij, qs, qd);
else if(mij<qs)return Query(nod*2+1, mij+1, dr, qs, qd);
return C(Query(nod*2, st, mij, qs, qd), Query(nod*2+1, mij+1, dr, qs, qd));
}
}
int main()
{ int n, m, a, b;
fin>>n>>m;
for(int i=1;i<=n;i++)
fin>>y[i];
Build(1, 1, n);
//for(int i=1;i<=n*3;i++)cout<<x[i].r<<" ";
for(int i=1;i<=m;i++)
{fin>>a>>b;
fout<<Query(1, 1, n, a, b).r<<"\n";
}
return 0;
}