#include <fstream>

#include <vector>

using namespace std;

struct tree_node {

    long long sum, pref_max, suf_max, smax;
};

vector<tree_node> segment_tree;

vector<int> v;

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_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.smax = max(max(left_node.smax, right_node.smax), left_node.suf_max + right_node.pref_max);

    return current_node;
}

void build(int node, int left, int right) {

    if (left == right) {

        segment_tree[node].sum = v[left];

        segment_tree[node].pref_max = v[left];

        segment_tree[node].suf_max = v[left];

        segment_tree[node].smax = v[left];
    }
    else {

        int middle = (left + right) / 2;

        build(2 * node, left, middle);

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

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

tree_node query(int node, int left, int right, int query_left, int query_right) {

    if (query_left <= left && right <= query_right)
        return segment_tree[node];
    else {

        int middle = (left + right) / 2;

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

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

        return update_node(left_node, right_node);
    }
}

int main() {

    ifstream fin("sequencequery.in");

    ofstream fout("sequencequery.out");

    int n, m;

    fin >> n >> m;

    v.resize(n + 1);

    for (int i = 1; i <= n; ++i)
        fin >> v[i];
    
    segment_tree.resize(4 * n);

    build(1, 1, n);

    for (int i = 1; i <= m; ++i) {

        int x, y;

        fin >> x >> y;

        fout << query(1, 1, n, x, y).smax << '\n';
    }

    return 0;
}