#include <bits/stdc++.h>
#define int long long

using namespace std;

ifstream fin("sequencequery.in");
ofstream fout("sequencequery.out");

int INF = -1e9;
int n, a[100005], m;

struct vrajeala /// Wizard
{
    int sum, smax, pref, suff;
};

struct WizardTower
{
    vector <vrajeala> aint;

    WizardTower(int n)
    {
        int sz = 1;
        while (sz < n)
            sz *= 2;
        aint.resize(2 * sz);
    }

    void Update(int CurrentNode, int left, int right, int poz, int val)
    {
        if (left > poz or right < poz)
            return;

        if (left == right)
        {
            vrajeala w;
            w = { val, val, val, val };
            aint[CurrentNode] = w;
            return;
        }

        int mij = (left + right) / 2, lson = 2 * CurrentNode, rson = 2 * CurrentNode + 1;
        Update(lson, left, mij, poz, val);
        Update(rson, mij + 1, right, poz, val);
        aint[CurrentNode].sum = aint[lson].sum + aint[rson].sum;
        aint[CurrentNode].smax = max( aint[lson].smax, aint[rson].smax );
        aint[CurrentNode].smax = max(aint[CurrentNode].smax, aint[lson].suff + aint[rson].pref);
        aint[CurrentNode].pref = max(aint[lson].pref, aint[lson].sum + aint[rson].pref);
        aint[CurrentNode].suff = max(aint[rson].suff, aint[rson].sum + aint[lson].suff);
    }

    void Update(int poz, int val)
    {
        Update(1, 1, n, poz, val);
    }

    vrajeala Query(int CurrentNode, int left, int right, int leftQuery, int rightQuery)
    {
        if (leftQuery > right or rightQuery < left)
            return { INF,INF,INF,INF };

        if (leftQuery <= left and right <= rightQuery)
            return aint[CurrentNode];

        int mij = (left + right) / 2, lson = 2 * CurrentNode, rson = 2 * CurrentNode + 1;
        vrajeala x1 = Query(lson, left, mij, leftQuery, rightQuery);
        vrajeala x2 = Query(rson, mij + 1, right, leftQuery, rightQuery);
        vrajeala w;
        w.sum = x1.sum + x2.sum;
        w.smax = max({ x1.smax, x2.smax, x1.suff + x2.pref });
        w.pref = max({ x1.pref, x1.sum + x2.pref });
        w.suff = max({ x2.suff, x2.sum + x1.suff });
        return w;
    }

    vrajeala Query(int leftQuery, int rightQuery)
    {
        return Query(1, 1, n, leftQuery, rightQuery);
    }
};

int32_t main() 
{
    int i, op, x, y;
    fin >> n >> m;
    WizardTower tower(n);
    for (i = 1; i <= n; i++)
    {
        fin >> a[i];
        tower.Update(i, a[i]);
    }

    while (m--)
    {
        fin >> x >> y;
        fout << tower.Query(x, y).smax << "\n";
    }

    return 0;
}