#include<bits/stdc++.h>
using namespace std;
ifstream in("sequencequery.in");
ofstream out("sequencequery.out");
const int N = 1e5;
const int INF = 1e9;
struct Nod
{
    long long prefix, sufix, smax, suma; ///smax = suma secventei de suma maxima, suma = suma intregii secvente
};
Nod aint[N * 4];
int fs(int nod) { return nod * 2; }
int fd(int nod) { return nod * 2 + 1; }
Nod make_nod(Nod nod_st, Nod nod_dr)
{
    Nod aux;
    aux.suma = nod_st.suma + nod_dr.suma;
    aux.prefix = max(nod_st.prefix, nod_st.suma + nod_dr.prefix );
    aux.sufix = max(nod_dr.sufix, nod_st.sufix + nod_dr.suma );
    aux.smax = max(nod_dr.smax, max(nod_st.smax, nod_st.sufix + nod_dr.prefix));
    return aux;
}
void build(int nod, int st, int dr, int idx, long long nr)
{
    if ( st == dr )
    {
        aint[nod] = {nr, nr, nr, nr};
        return;
    }
    int mij = ( st + dr ) / 2;
    if ( idx <= mij )
    {
        build(fs(nod), st, mij, idx, nr);
    }
    else
    {
        build(fd(nod), mij + 1, dr, idx, nr);
    }
    aint[nod] = make_nod(aint[fs(nod)], aint[fd(nod)]);
}
Nod query(int nod, int st, int dr, int qs, int qd)
{
    if ( st > qd || dr < qs )
    {
        Nod aux = {-INF, -INF, -INF, -INF};
        return aux;
    }
    if ( qs <= st && dr <= qd )
    {
        return aint[nod];
    }
    int mij = ( st + dr ) / 2;
    return make_nod(query(fs(nod), st, mij, qs, qd), query(fd(nod), mij + 1, dr, qs, qd));
}
int n, m;
void citire()
{
    in>>n>>m;
    for ( int i = 1 ; i <= n ; i++ )
    {
        long long x;
        in>>x;
        build(1, 1, n, i, x);
    }
}
void rez()
{
    for ( int i = 1 ; i <= m ; i++ )
    {
        int x, y;
        in>>x>>y;
        out<<query(1, 1, n, x, y).smax<<'\n';
    }
}
int main()
{
    citire();
    rez();
    return 0;
}