#include <fstream>
#define DIM 100002

using namespace std;

ifstream f("sequencequery.in");
ofstream g("sequencequery.out");

int i, n, m, ok, v[DIM], a, b;

struct abc
{
    long long smax, sst, sdr, stot;
}sol, arb[3 * DIM], zero;

void build(int nod, int st, int dr)
{
    if(st == dr)
    {
        abc aux;
        aux.smax = aux.sst = aux.sdr = aux.stot = v[st];
        arb[nod] = aux;
    }
    else
    {
        int mid = (st + dr) / 2;
        build(2 * nod, st, mid);
        build(2 * nod + 1, mid + 1, dr);
        arb[nod].smax = max(arb[2 * nod].smax, max(arb[2 * nod + 1].smax, arb[2 * nod].sdr + arb[2 * nod + 1].sst));
        arb[nod].sst = max(arb[2 * nod].sst, arb[2 * nod].stot + arb[2 * nod + 1].sst);
        arb[nod].sdr = max(arb[2 * nod + 1].sdr, arb[2 * nod + 1].stot + arb[2 * nod].sdr);
        arb[nod].stot = arb[2 * nod].stot + arb[2 * nod + 1].stot;
    }
}

void query(int nod, int st, int dr, int a, int b)
{
    if(a <= st && b >= dr)
    {
        if(ok == 0)
        {
            sol = arb[nod];
            ok = 1;
        }
        else
        {
            sol.smax = max(arb[nod].smax, max(sol.smax, arb[nod].sst + sol.sdr));
            sol.sst = max(sol.sst, sol.sst + arb[nod].stot);
            sol.sdr = max(sol.sdr + arb[nod].stot, arb[nod].sdr);
            sol.stot += arb[nod].stot;
        }
    }
    else
    {
        int mid = (st + dr) / 2;
        if(a <= mid)
            query(2 * nod, st, mid, a, b);
        if(b > mid)
            query(2 * nod + 1, mid + 1, dr, a, b);
    }
}

int main()
{

    f>>n>>m;

    for(i = 1;i <= n; ++ i)
        f>>v[i];

    build(1, 1, n);

    zero.sst = zero.sdr = zero.stot = zero.smax = 0;

    for(i = 1;i <= m; ++ i)
    {
        f>>a>>b;
        sol = zero;
        ok = 0;
        query(1, 1, n, a, b);
        g<<sol.smax<<'\n';
    }

    return 0;
}