#include <iostream>
#include <fstream>
#include <algorithm>
#define fs(i) i << 1
#define fd(i) (i << 1) + 1
#define maxN 100005 * 4

using namespace std;

struct nod{
    long long r, pref, suf, s;
} A[maxN];


void update(int l, int r, int i, int p, int v)
{
    if (l == r)
    {
        A[i].pref = A[i].suf = A[i].r = A[i].s = v;
        return;
    }

    int m = (l+r)>>1;
    if (p <= m) update(l, m, fs(i), p, v);
           else update(m + 1, r, fd(i), p, v);

    A[i].r=max(max(A[fs(i)].r, A[fd(i)].r), A[fs(i)].suf + A[fd(i)].pref);
    A[i].pref=max(A[fs(i)].pref, A[fs(i)].s + A[fd(i)].pref);
    A[i].suf=max(A[fd(i)].suf, A[fd(i)].s + A[fs(i)].suf);
    A[i].s=A[fs(i)].s + A[fd(i)].s;
}

nod vezi(int l, int r, int a, int b, int i){

    if (l >= a && r <= b)
        return A[i];

    nod v1, v2, v3;
    int m = (l + r) >> 1;

    v1.r = v1.pref = v1.suf = v1.s = -500000;
    v2.r = v2.pref = v2.suf = v2.s = -500000;

    if (a <= m) v1 = vezi(l, m, a, b, fs(i));
    if (b > m) v2 = vezi(m + 1, r, a, b, fd(i));

    v3.r = max(max(v1.r, v2.r), v1.suf + v2.pref);
    v3.pref = max(v1.pref, v1.s + v2.pref);
    v3.suf = max(v2.suf, v2.s + v1.suf);
    v3.s = v1.s + v2.s;
    return v3;
}

int main()
{
    int i,j;
    ifstream f("sequencequery.in");
    ofstream g("sequencequery.out");

    int n, m;

    f >> n >> m;

    for (int i = 1; i <= n; ++i){
        int x;
        f >> x;
        update(1, n, 1, i, x);
    }


    for (int i = 0; i < m; ++i){
        int x, y;
        nod d;
        f >> x >> y;
        d = vezi(1, n, x, y, 1);
        g << d.r << "\n";
    }

    f.close();
    g.close();

    return 0;
}