#include <fstream>

using namespace std;

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

struct tree
{
    long long sum, pref_max, suf_max, scmax;
};
int n, m;
int v[100005];
tree segtree[400005];

tree update_node(tree left_node, tree right_node)
{
    tree current_node;

    current_node.sum = left_node.sum + right_node.sum;

    current_node.pref_max = max(left_node.pref_max, left_node.sum + right_node.pref_max);

    current_node.suf_max = max(right_node.suf_max, right_node.sum + left_node.suf_max);

    current_node.scmax = max(left_node.suf_max + right_node.pref_max, max(left_node.scmax, right_node.scmax));

    return current_node;
}

void build(int node, int left, int right)
{
    if(left == right)
    {
        segtree[node].sum = v[left];
        segtree[node].pref_max = v[left];
        segtree[node].suf_max = v[left];
        segtree[node].scmax = v[left];
    }
    else
    {
        int m = (left + right) / 2;

        build(2*node, left, m);
        build(2*node+1, m+1, right);

        segtree[node] = update_node(segtree[2*node], segtree[2*node+1]);
    }
}

tree query(int node, int left, int right, int qleft, int qright)
{
    if(qleft <= left && right <= qright)
    {
        return segtree[node];
    }
    else
    {
        int m = (left + right) / 2;

        if(qright <= m)
        {
            return query(2*node, left, m, qleft, qright);
        }
        if(m+1 <= qleft)
        {
            return query(2*node+1, m+1, right, qleft, qright);
        }

        tree left_node = query(2*node, left, m, qleft, qright);
        tree right_node = query(2*node+1, m+1, right, qleft, qright);

        return update_node(left_node, right_node);
    }
}

int main()
{
    in>>n>>m;

    for(int i = 1; i<=n; i++)
    {
        in>>v[i];
    }

    build(1, 1, n);

    int st, dr;
    while(m--)
    {
        in>>st>>dr;
        out<<query(1, 1, n, st, dr).scmax<<'\n';
    }

    return 0;
}