#include <fstream>

using namespace std;

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

const int NMAX = 100000;

const int INF = 1e9;

int v[NMAX + 5];

struct Nod
{
    long long pre, suf, sumax, sum;
};

struct Aint
{

    Nod a[4 * NMAX];
    void Build(int first, int last, int i)
    {
        if(first == last)
        {
            a[i].sum = v[first];
            a[i].sumax = v[first];
            a[i].pre = v[first];
            a[i].suf = v[first];
            return;
        }

        int mid = (first + last) / 2;
        Build(first, mid, 2 * i);
        Build(mid + 1, last, 2 * i + 1);

        a[i].sum = a[2 * i].sum + a[2 * i + 1].sum;
        a[i].pre = max(a[2 * i].pre, a[2 * i].sum + a[2 * i + 1].pre);
        a[i].suf = max(a[2 * i + 1].suf, a[2 * i + 1].sum + a[2 * i].suf);
        a[i].sumax = max(a[2 * i].suf + a[2 * i + 1].pre, max(a[2 * i].sumax, a[2 * i + 1].sumax));
    }

    Nod Query(int i, int first, int last, int left, int right)
    {
        if(first >= left && last <= right)
            return a[i];
        if(first > right || last < left)
            return {-INF, -INF, -INF, -INF};

        int mid = (first + last) / 2;


        Nod nod;

        Nod aux1 = Query(2 * i, first, mid, left, right);
        Nod aux2 = Query(2 * i + 1, mid + 1, last, left, right);
        nod.sum = aux1.sum + aux2.sum;
        nod.pre = max(aux1.pre, aux1.sum + aux2.pre);
        nod.suf = max(aux2.suf, aux2.sum + aux1.suf);
        nod.sumax = max(aux1.suf + aux2.pre, max(aux1.sumax, aux2.sumax));

        return  nod;
    }

};

Aint Arb;


int main()
{
    int n, m, q, x, y;
    fin >> n >> m;
    for(int i = 1; i <= n; i++)
        fin >> v[i];

    Arb.Build(1, n, 1);

    for(int i = 0; i < m; i++)
    {
        fin >> x >> y;
        fout << (Arb.Query(1, 1, n, x, y)).sumax << '\n' ;
    }
    return 0;
}