#include <fstream>
#include <climits>

using namespace std;

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

const int DIM = 100010;

int n, m, x, y, sol;
int v[DIM];

struct treeNode {
    long long sum;
    long long maxSumPref;
    long long maxSumSuff;
    long long maxSumSubseq;
} tree[4 * DIM];

void updateNode(treeNode& node, treeNode leftNode, treeNode rightNode) {
    node.sum = leftNode.sum + rightNode.sum;
    node.maxSumPref = max(leftNode.maxSumPref, leftNode.sum + rightNode.maxSumPref);
    node.maxSumSuff = max(rightNode.maxSumSuff, leftNode.maxSumSuff + rightNode.sum);
    node.maxSumSubseq = max(max(leftNode.maxSumSubseq, rightNode.maxSumSubseq),
                                  leftNode.maxSumSuff + rightNode.maxSumPref);
}

void build(int node, int left, int right) {
    if (left == right) {
        tree[node] = { v[left], v[left], v[left], v[left] };
    } else {
        int middle = (left + right) / 2;
        build(2 * node, left, middle);
        build(2 * node + 1, middle + 1, right);
        updateNode(tree[node], tree[2 * node], tree[2 * node + 1]);
    }
}

treeNode query(int node, int left, int right, int qLeft, int qRight) {
    if (qLeft <= left && right <= qRight)
        return tree[node];

    int middle = (left + right) / 2;

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

    treeNode leftNode = query(2 * node, left, middle, qLeft, qRight);
    treeNode rightNode = query(2 * node + 1, middle + 1, right, qLeft, qRight);

    updateNode(tree[node], leftNode, rightNode);
    return tree[node];
}

int main() {
    fin >> n >> m;
    for (int i = 1; i <= n; i++)
        fin >> v[i];

    build(1, 1, n);

    for (int i = 1; i <= m; i++) {
        fin >> x >> y;
        fout << query(1, 1, n, x, y).maxSumSubseq << '\n';
    }

    return 0;
}