#include <bits/stdc++.h>

using namespace std;

class SegmentTreeTraverser {
    typedef function<bool (int, int, int)> Callback;

    enum NodeState {
        PENDING_EXTRACTION = 0,
        PENDING_DELETION = 1
    };

    size_t m_size;

    Callback m_onNodeStart;
    Callback m_onNodeEnd;
    Callback m_onLeaf;

    bool contains_range(int left, int right, const pair<int, int> &range) {
        return range.first <= left && right <= range.second;
    }

public:
    SegmentTreeTraverser(size_t size, 
                         Callback onLeaf,
                         Callback onNodeStart, 
                         Callback onNodeEnd) : 
            m_size(size),
            m_onLeaf(onLeaf),
            m_onNodeStart(onNodeStart),
            m_onNodeEnd(onNodeEnd) {}

    void traverse(const pair<size_t, size_t> &range, bool all_nodes=false) {
        stack<pair<NodeState, tuple<int, int, int>>> node_stack;

        node_stack.push({PENDING_EXTRACTION, make_tuple(1, 0, m_size - 1)});

        while (!node_stack.empty()) {
            auto current_node = node_stack.top(); node_stack.pop();
            int pos = get<0>(current_node.second);
            int left = get<1>(current_node.second);
            int right = get<2>(current_node.second);
            int mid = left + (right - left) / 2;

            switch (current_node.first) {
                case PENDING_EXTRACTION:

                    if (m_onNodeStart(pos, left, right)) {
                        node_stack.push({PENDING_DELETION, current_node.second});

                        if (all_nodes || !contains_range(left, right, range)) {
                            if (range.second > mid) {
                                node_stack.push({PENDING_EXTRACTION, make_tuple(2 * pos + 1, mid + 1, right)});
                            }
                            if (range.first <= mid) {
                                node_stack.push({PENDING_EXTRACTION, make_tuple(2 * pos, left, mid)});
                            }
                        } else {
                            m_onLeaf(pos, left, right);
                        }
                    }

                break;

                case PENDING_DELETION:
                    if (all_nodes || !contains_range(left, right, range)) {
                        m_onNodeEnd(pos, left, right);
                    }
                break;
            }
        }
    }
};

auto EMPTY = [](int, int, int) -> bool {return true;};

class SegmentMaxSubseq {

    const static int inf = 0x3f3f3f3f;

    struct Node {
        int sol;
        int left;
        int right;
        int sum;
    };

    size_t m_size;
    vector<Node> arb;

    void make(const vector<int> &vec) {
        arb.resize(4 * vec.size());
        m_size = vec.size();

        SegmentTreeTraverser stt(m_size,
            EMPTY,
            [&](int pos, int left, int right) -> bool {
                if (left == right) {
                    arb[pos].sum = arb[pos].left = 
                    arb[pos].right = arb[pos].sol = vec[left];
                    return false;
                }
                return true;
            },
            [&](int pos, int left, int right) -> bool {
                if (left != right) {
                    arb[pos] = combine(arb[2 * pos], arb[2 * pos + 1]);
                }
            });

        stt.traverse({0, m_size - 1}, true);
    }

public:

    SegmentMaxSubseq(const vector<int> &vect) {
        make(vect);
    }

    Node combine(const Node &left, const Node & right) {
        Node ans;

        ans.sum = left.sum + right.sum;
        ans.left = max(left.left, left.sum + right.left);
        ans.right = max(right.right, right.sum + left.right);
        ans.sol = max(max(left.sol, right.sol), left.right + right.left);

        return ans;
    }

    int query(const pair<int, int> &range) {
        Node ans = {-inf, -inf, -inf, 0};

        SegmentTreeTraverser stt(m_size,
            [&](int pos, int left, int right) -> bool {
                // cerr << left << " " << right << endl;
                ans = combine(ans, arb[pos]);
                // cerr << ans.sol << endl;
            }, EMPTY, EMPTY);

        stt.traverse(range);

        return ans.sol;
    }
};

int main() {
    freopen("sequencequery.in", "r", stdin);
    freopen("sequencequery.out", "w", stdout);

    int n, m;
    cin >> n >> m;

    vector<int> vec(n);
    for (int i = 0; i < n; ++ i) {
        cin >> vec[i];
    }

    SegmentMaxSubseq sms(vec);

    for (int i = 0; i < m; ++ i) {
        int x, y;
        cin >> x >> y;

        cout << sms.query({x - 1, y - 1}) << endl;
    }

    return 0;
}