#include <fstream>
#include <algorithm>

using namespace std;

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

const int N = 100000;;

struct tree_node
{
    long long sum;
    long long pref_scmax;
    long long suff_scmax;
    long long scmax;
};

int array[N + 1];
tree_node segment_tree[N * 4 + 1];

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

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

    current_node.pref_scmax =
        std::max(left_node.pref_scmax,
                 left_node.sum + right_node.pref_scmax);

    current_node.suff_scmax =
        std::max(right_node.suff_scmax,
                 right_node.sum + left_node.suff_scmax);

    current_node.scmax =
        std::max(left_node.suff_scmax + right_node.pref_scmax,
                 std::max(left_node.scmax, right_node.scmax));

    return current_node;
}

void build(int node, int left, int right)
{
    if (left == right)
    {
        segment_tree[node].sum = array[left];
        segment_tree[node].pref_scmax = array[left];
        segment_tree[node].suff_scmax = array[left];
        segment_tree[node].scmax = array[left];
    }
    else
    {
        int middle = (left + right) / 2;

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

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

tree_node query(int node, int left, int right, int query_left, int query_right)
{
    if (query_left <= left and right <= query_right)
    {
        return segment_tree[node];
    }
    else
    {
        int middle = (left + right) / 2;

        if (query_right <= middle)
            return query(node * 2, left, middle, query_left, query_right);
        if (middle + 1 <= query_left)
            return query(node * 2 + 1, middle + 1, right, query_left, query_right);

        tree_node left_node = query(node * 2, left, middle, query_left, query_right),
                  right_node = query(node * 2 + 1, middle + 1, right, query_left, query_right);

        return update_node(left_node, right_node);
    }
}

int main()
{

    int n, q;
    in >> n >> q;

    for (int i = 1; i <= n; ++i)
        in >> array[i];

    build(1, 1, n);

    while (q--)
    {
        int left, right;
        in >> left >> right;
        out << query(1, 1, n, left, right).scmax << "\n";
    }

    return 0;
}