#include <bits/stdc++.h>
using namespace std;

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

class SegmTree {
  private:
    struct Node {
        int64_t sumAll, maxSum;
        int64_t maxLeft, maxRight;

        Node(int64_t val = 0) {
            sumAll = maxSum = maxLeft = maxRight = val;
        }

        Node operator+(Node right) {
            Node ret;
            ret.sumAll = sumAll + right.sumAll;
            ret.maxSum = max(maxRight + right.maxLeft, max(maxSum, right.maxSum));
            ret.maxLeft = max(maxLeft, sumAll + right.maxLeft);
            ret.maxRight = max(right.maxRight, right.sumAll + maxRight);
            return ret;
        }
    };

    int n;
    vector<Node> tree;

    void build(int node, int left, int right, vector<int64_t>& v) {
        if (left == right) {
            tree[node] = Node(v[left]);
            return;
        }

        int mid = (left + right) / 2;
        build(2 * node, left, mid, v);
        build(2 * node + 1, mid + 1, right, v);
        tree[node] = tree[2 * node] + tree[2 * node + 1];
    }

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

        int mid = (left + right) / 2;
        if (qRight <= mid)
            return query(2 * node, left, mid, qLeft, qRight);
        if (qLeft > mid)
            return query(2 * node + 1, mid + 1, right, qLeft, qRight);

        return query(2 * node, left, mid, qLeft, mid) +
               query(2 * node + 1, mid + 1, right, mid + 1, qRight);
    }

  public:
    SegmTree(vector<int64_t>& v) {
        n = v.size() - 1;
        tree.resize(4 * n);
        build(1, 1, n, v);
    }

    int64_t query(int left, int right) {
        return query(1, 1, n, left, right).maxSum;
    }
};

int main() {
    int n, q;
    fin >> n >> q;

    vector<int64_t> v(n + 1);
    for (int i = 1; i <= n; i++)
        fin >> v[i];
    SegmTree tree(v);

    for (int i = 0; i < q; i++) {
        int x, y; fin >> x >> y;
        fout << tree.query(x, y) << '\n';
    }

    fout.close();
    return 0;
}