#include <fstream>
using namespace std;
ifstream in("sequencequery.in");
ofstream out("sequencequery.out");
const int N=1<<18;
struct nod{
long long total, prefix, sufix, smax;
};
nod t[N];
bool completat[N];
long long max(long long a, long long b, long long c)
{
return max(a, max(b,c));
}
nod combin(nod x, nod y)
{
nod rez;
rez.total=x.total+y.total;
rez.prefix=max(x.prefix, x.total+y.prefix);
rez.sufix=max(y.sufix, x.sufix+y.total);
rez.smax=max(x.smax, y.smax, x.sufix+y.prefix);
return rez;
}
void actualizare(int p, int st, int dr, int poz, int val)
{
if(st==dr)
{
t[p].prefix=t[p].smax=t[p].sufix=t[p].total=val;
completat[p]=true;
return;
}
int m=(st+dr)/2,fs=2*p,fd=2*p+1; ///fs=fiu stang; fd=fiu drept
if(poz<=m)
{
actualizare(fs, st, m ,poz, val);
}
else
{
actualizare(fd, m+1, dr ,poz, val);
}
if(completat[fs] && completat[fd])
{
t[p]=combin(t[fs], t[fd]);
}
else if(completat[fs])
{
t[p]=t[fs];
}
else
{
t[p]=t[fd];
}
completat[p]=true;
}
nod interogare(int p, int st, int dr, int a, int b)
{
if(a<=st && dr<=b)
{
return t[p];
}
int m=(st+dr)/2,fs=2*p,fd=2*p+1;
if(a<=m && b>m) ///[a,b] se intersecteaza cu ambii fii
{
nod q_st=interogare(fs, st, m, a, b);
nod q_dr=interogare(fd, m+1, dr, a, b);
return combin(q_st, q_dr);
}
if(a<=m)
{
return interogare(fs, st, m, a, b);
}
return interogare(fd, m+1, dr, a, b);
}
int main()
{
int n,m;
in>>n>>m;
for(int i=1; i<=n; i++)
{
int aux;
in>>aux;
actualizare(1, 1, n, i, aux);
}
for(int i=0; i<m; i++)
{
int a,b;
in>>a>>b;
nod rez=interogare(1, 1, n, a, b);
out<<rez.smax<<"\n";
}
in.close();
out.close();
return 0;
}