#include <fstream>
using namespace std;
ifstream in("sequencequery.in");
ofstream out("sequencequery.out");
const int N = 1 + (1<<18);
const long long INF = (long long)1<<30;
struct nod
{
long long st,dr,max,tot;
};
int n,m,v[N],a,b;
nod t[N];
inline int fs(int p)
{
return p<<1;
}
inline int fd(int p)
{
return (p<<1)+1;
}
inline long long max(long long x, long long y)
{
return x>y ? x : y;
}
void modifica(int p, int st, int dr, int poz, long long val)
{
if(st == dr)
{
t[p].st = t[p].dr = t[p].max = t[p].tot = val;
return;
}
int mij = (st+dr)>>1;
if(poz <= mij)
modifica(fs(p), st, mij, poz, val);
if(poz > mij)
modifica(fd(p), mij+1, dr, poz, val);
t[p].st = max(t[fs(p)].st, t[fs(p)].tot + t[fd(p)].st);
t[p].dr = max(t[fd(p)].dr, t[fd(p)].tot + t[fs(p)].dr);
t[p].max = max(t[fs(p)].dr + t[fd(p)].st, max(t[fs(p)].max, t[fd(p)].max));
t[p].tot = t[fs(p)].tot + t[fd(p)].tot;
}
inline void init(nod &p)
{
p.st = p.dr = p.max = p.tot = (-INF);
}
nod raspunde(int p, int st, int dr)
{
if(a<=st && dr<=b)
return t[p];
int mij = (st+dr) >> 1;
nod pc, ps, pd;
init(ps);
init(pd);
if(a <= mij)
ps = raspunde(fs(p), st, mij);
if(b > mij)
pd = raspunde(fd(p), mij+1, dr);
pc.st = max(ps.st, ps.tot + pd.st);
pc.dr = max(pd.dr, pd.tot + ps.dr);
pc.max = max(ps.dr + pd.st, max(ps.max, pd.max));
pc.tot = ps.tot + pd.tot;
return pc;
}
void scrie(int p, int st, int dr)
{
out<<p<<": ["<<st<<","<<dr<<"] -> st="<<t[p].st<<",\tdr="<<t[p].dr<<",\tmax="<<t[p].max<<"\n";
if(st == dr)
return;
int mij = (st+dr) >> 1;
scrie(fs(p), st, mij);
scrie(fd(p), mij+1, dr);
}
int main()
{
in>>n>>m;
for(int i=1; i<=n; i++)
modifica(1, 1, n, i, -INF);
for(int i=1; i<=n; i++)
{
in>>v[i];
modifica(1, 1, n, i, (long long)v[i]);
//out<<"\nadaug "<<v[i]<<" pe pozitia "<<i<<"\n";
//scrie(1, 1, n);
}
//scrie(1, 1, n);
for(int i=1; i<=m; i++)
{
in>>a>>b;
out<<raspunde(1, 1, n).max<<"\n";
}
return 0;
}