#include <iostream>
#include <fstream>

using namespace std;

const int nmax = 1e5;
int a[5 + nmax];

struct Aint {
    struct Node {
        int pref, suff, sum, maxsum;

        Node() {
            pref = 0;
            suff = 0;
            sum = 0;
            maxsum = 0;
        }
        Node(int _pref, int _suff, int _sum, int _maxsum) {
            pref = _pref;
            suff = _suff;
            sum = _sum;
            maxsum = _maxsum;
        }
    };
    
    Node segtree[5 + 4 * nmax];

    Node join(Node left, Node right) {
        Node ret;
        ret.pref = max(left.pref, left.sum + right.pref);
        ret.suff = max(right.suff, right.sum + left.suff);
        ret.sum = left.sum + right.sum;
        ret.maxsum = max({left.maxsum, right.maxsum, left.suff + right.pref});
        return ret;
    }

    void build(int node, int left, int right) {
        if (left == right) {
            segtree[node].pref = a[left];
            segtree[node].suff = a[left];
            segtree[node].sum = a[left];
            segtree[node].maxsum = a[left];
            return;
        }
        int middle = (left + right) / 2;
        build(2 * node, left, middle);
        build(2 * node + 1, middle + 1, right);
        segtree[node] = join(segtree[2 * node], segtree[2 * node + 1]);
    }

    Node query(int node, int left, int right, int qleft, int qright) {
        if (qleft <= left && right <= qright) {
            return segtree[node];
        }
        int middle = (left + right) / 2;
        if (qleft <= middle && middle < qright) {
            return join(query(2 * node, left, middle, qleft, qright),
                        query(2 * node + 1, middle + 1, right, qleft, qright));
        }
        if (qleft <= middle) {
            return query(2 * node, left, middle, qleft, qright);
        }
        if (middle < qright) {
            return query(2 * node + 1, middle + 1, right, qleft, qright);
        }
        return Node {-1, -1, -1, -1};
    }
};

signed main() {
    ifstream fin("sequencequery.in");
    ofstream fout("sequencequery.out");
    int n, m;
    fin >> n >> m;
    for (int i = 1; i <= n; i++) {
        fin >> a[i];
    }
    Aint aint;
    aint.build(1, 1, n);
    while (m--) {
        int left, right;
        fin >> left >> right;
        fout << aint.query(1, 1, n, left, right).maxsum << '\n';
    }
    return 0;
}