#include <iostream>
#include <fstream>
using namespace std;

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

struct Node {
    long long sp = 0;
    long long stmax = -2e10;
    long long drmax = -2e10;
    long long smax = -2e10;
};

class SegmentTree {
public:
    Node *tree;
    int size;

    SegmentTree(int n) {
        size = n;
        tree = new Node[n * 4]();
    }

    void Update(int n, int start, int end, int pos, int val) {
        if (start == end) {
            tree[n].sp = val;
            tree[n].stmax = val;
            tree[n].drmax = val;
            tree[n].smax = val;
            return;
        }

        int mid = (start + end) / 2;
        if (pos <= mid)
            Update(n * 2, start, mid, pos, val);
        else
            Update(n * 2 + 1, mid + 1, end, pos, val);

        tree[n].sp = tree[n * 2].sp + tree[n * 2 + 1].sp;
        tree[n].stmax = max(tree[n * 2].stmax, tree[n * 2].sp + tree[n * 2 + 1].stmax);
        tree[n].drmax = max(tree[n * 2 + 1].drmax, tree[n * 2 + 1].sp + tree[n * 2].drmax);
        tree[n].smax = max(tree[n].smax, tree[n].stmax);
        tree[n].smax = max(tree[n].smax, tree[n].drmax);
        tree[n].smax = max(tree[n].smax, tree[n].sp);
        tree[n].smax = max(tree[n].smax, tree[n * 2].smax);
        tree[n].smax = max(tree[n].smax, tree[n * 2 + 1].smax);
        tree[n].smax = max(tree[n].smax, tree[n * 2].drmax + tree[n * 2 + 1].stmax);
    }

    Node Query(int n, int start, int end, int a, int b) {
        //cout << start << " " << end << " " << a << " " << b << endl;
        if (start >= a && end <= b) {
            return tree[n];
        }

        Node sol, left, right;
        int mid = (start + end) / 2;

        if (a <= mid) {
            left = Query(n * 2, start, mid, a, b);
        }
        if (b > mid) {
            right = Query(n * 2 + 1, mid + 1, end, a, b);
        }

        sol.sp = left.sp + right.sp;
        sol.stmax = max(left.stmax, left.sp + right.stmax);
        sol.drmax = max(right.drmax, right.sp + left.drmax);
        sol.smax = max(sol.smax, sol.stmax);
        sol.smax = max(sol.smax, sol.drmax);
        sol.smax = max(sol.smax, sol.sp);
        sol.smax = max(sol.smax, left.smax);
        sol.smax = max(sol.smax, right.smax);
        sol.smax = max(sol.smax, left.drmax + right.stmax);
        return sol;
    }
};


int n, m;
SegmentTree *T;


int main() {
    //in >> n;
    in >> n >> m;
    T = new SegmentTree(n);

    for (int i = 1, x; i <= n; ++i) {
        in >> x;
        T -> Update(1, 1, n, i, x);
    }


    //in >> m;
    for (int i = 1, o, x, y; i <= m; ++i) {
        //in >> o >> x >> y;
        in >> x >> y;
        /*if (o == 0) {
            T -> Update(1, 1, n, x + 1, y);
        } else {
            Node nod = T -> Query(1, 1, n, x + 1, y + 1);
            if (nod.smax < 0) out << 0 << '\n';
                else out << nod.smax << '\n';
        }*/
        Node nod = T -> Query(1, 1, n, x, y);
        out << nod.smax << '\n';
    }

}