#include <fstream>

using namespace std;
ifstream f("sequencequery.in");
ofstream g("sequencequery.out");
int n , m , x , y , i;
int gx , val , gl , gr;
long long smax , suma , SM;
struct valoare
{
    long long sumaL , sumaR , smax , suma;
};
valoare arb[800005];
void update(int nod,int st,int dr)
{
    if(st == dr)
    {
        arb[nod].smax = arb[nod].sumaL = arb[nod].sumaR = val;
        arb[nod].suma = val;
        return;
    }
    int mij = (st + dr) / 2;
    if (mij >= gx)
        update(2 * nod , st , mij);
    else update(2 * nod + 1,mij + 1,dr);
    arb[nod].suma = arb[2 * nod].suma + arb[2 * nod + 1].suma;
    arb[nod].sumaL = max(arb[2 * nod + 1].sumaL,arb[2 * nod].sumaL + arb[2 * nod + 1].suma);
    arb[nod].sumaR = max(arb[2*nod].sumaR,arb[2 * nod].suma + arb[2 * nod + 1].sumaR);
    arb[nod].smax = max(max(arb[2 * nod].smax,arb[2 * nod + 1].smax),arb[2 * nod].sumaL + arb[2 * nod + 1].sumaR);
}
void query(int nod,int st,int dr)
{
    if(gl <= st && dr <= gr)
    {
        smax = max(arb[nod].smax , suma + arb[nod].sumaR);
        suma = max((suma + arb[nod].suma) , arb[nod].sumaL);
        SM = max(SM , max(suma , smax));
        return;
    }
    int mij = (st + dr) / 2;
    if(gl <= mij)
        query(2 * nod , st , mij);
    if(mij < gr)query(2 * nod + 1,mij + 1,dr);
}
int main()
{
    f>>n>>m;
    for(i = 1; i <= n; i++)
    {
        f>>x;
        gx = i;
        val = x;
        update(1 , 1 , n);
    }
    for(i = 1; i <= m; i++)
    {
        f>>x>>y;
        smax = suma = SM = -100000;
        gl = x;
        gr = y;
        query(1 , 1 , n);
        g << SM << '\n';
    }
    return 0;
}