#include <fstream>

using namespace std;

    ifstream cin("sequencequery.in");
    ofstream cout("sequencequery.out");
    typedef long long ll;
    const int dim = 100001;
    struct nod
    {
        ll pref;
        ll suf;
        ll sum;
        ll secv;
    };
    int v[dim];
    nod A[4 * dim];

    nod up_node(nod left, nod right)
    {
        nod aux;
        aux.sum = left.sum + right.sum;
        aux.pref = max(left.pref, left.sum + right.pref);
        aux.suf = max(right.suf, right.sum + left.suf);
        aux.secv = max(right.pref + left.suf, max(left.secv, right.secv));
        return aux;
    }

    void build(int nod, int left, int right)
    {
        if (right == left)
        {
            A[nod].sum = v[left];
            A[nod].suf = v[left];
            A[nod].pref = v[left];
            A[nod].secv = v[left];
        }
        else
        {
            int mid = (left + right) >> 1;
            build(nod * 2, left, mid);
            build(nod * 2 + 1, mid + 1, right);
            A[nod] = up_node(A[nod * 2], A[nod * 2 + 1]);
        }
    }

    nod query(int node, int left, int right, int a, int b)
    {
        if (left >= a && right <= b)
            return A[node];
        else
        {
            int mid  = (left + right) >> 1;
            nod l, r;
            if (b <= mid)
                return query(node * 2, left, mid, a, b);
            if (a > mid)
                return query(node * 2 + 1, mid + 1, right, a, b);
            l = query(node * 2, left, mid, a, b);
            r = query(node * 2 + 1, mid + 1, right, a, b);
            return up_node(l, r);
        }
    }

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

    for (i = 1; i <= m; ++i)
    {
        cin >> x >> y;
        cout << query(1, 1, n, x, y).secv << '\n';
    }
    return 0;
}