#include <bits/stdc++.h>
#define DIM 100005
#define ll long long

using namespace std;

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

struct elem
{
    ll s, sdr, sst, smax;
}aint[4 * DIM];

int n, q, v[DIM];

void Build(int nod, int st, int dr)
{
    if(st == dr)
    {
        aint[nod] = {v[st], v[st], v[st], v[st]};
        return ;
    }

    int mid = (st + dr) / 2;
    Build(2 * nod, st, mid);
    Build(2 * nod + 1, mid + 1, dr);

    aint[nod].s = aint[2 * nod].s + aint[2 * nod + 1].s;
    aint[nod].sst = max(aint[2 * nod].sst, aint[2 * nod].s + aint[2 * nod + 1].sst);
    aint[nod].sdr = max(aint[2 * nod + 1].sdr, aint[2 * nod].sdr + aint[2 * nod + 1].s);
    aint[nod].smax = max(aint[2 * nod].smax, max(aint[2 * nod + 1].smax, aint[2 * nod].sdr + aint[2 * nod + 1].sst));
}

void Update(int nod, int st, int dr, int val, int poz)
{
    if(st == dr)
    {
        aint[nod] = {val, val, val, val};
        return ;
    }

    int mid = (st + dr) / 2;
    if(mid >= poz)
        Update(2 * nod, st, mid, val, poz);
    else
        Update(2 * nod + 1, mid + 1, dr, val, poz);


    aint[nod].s = aint[2 * nod].s + aint[2 * nod + 1].s;
    aint[nod].sst = max(aint[2 * nod].sst, aint[2 * nod].s + aint[2 * nod + 1].sst);
    aint[nod].sdr = max(aint[2 * nod + 1].sdr, aint[2 * nod].sdr + aint[2 * nod + 1].s);
    aint[nod].smax = max(aint[2 * nod].smax, max(aint[2 * nod + 1].smax, aint[2 * nod].sdr + aint[2 * nod + 1].sst));
}

elem Query(int nod, int st, int dr, int stQ, int drQ)
{
    if(stQ <= st && dr <= drQ)
    {
        return aint[nod];
    }

    int mid = (st + dr) / 2;
    bool okst = 0, okdr = 0;
    elem r, left, right;
    if(mid >= stQ)
    {
        left = Query(2 * nod, st, mid, stQ, drQ);
        okst = 1;
    }
    if(mid < drQ)
    {
        right = Query(2 * nod + 1, mid + 1, dr, stQ, drQ);
        okdr = 1;
    }

    if(okst == 0)
        return right;
    if(okdr == 0)
        return left;
    r.s = right.s + left.s;
    r.sst = max(left.sst, left.s + right.sst);
    r.sdr = max(right.sdr, left.sdr + right.s);
    r.smax = max(left.smax, max(right.smax, left.sdr + right.sst));

    return r;
}

int main()
{
    f >> n >> q;
    for(int i = 1; i <= n; i++)
        f >> v[i];
    Build(1, 1, n);

    for(; q; q--)
    {
        int x, y;
        f >> x >> y;
        g << Query(1, 1, n, x, y).smax << "\n";
    }

    return 0;
}