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

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

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

long long max(long long a, long long b, long long c, long long d) {
    return max(a, max(b, max(c, d)));
}

Node merge(Node left, Node right) {
    Node sol;
    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.sp, left.smax, right.smax, left.drmax + right.stmax);
    return sol;
}

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] = merge(tree[n * 2], tree[n * 2 + 1]);
    }

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

        Node 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);
        }

        return merge(left, right);
    }
};


int n, m;
SegmentTree *T;


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

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


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

    }

}