#include <fstream>
using namespace std;

const int MAX_N = 100002;

struct Node {
    long long int leftSum, rightSum, totalSum, ans;
};

int N, M;
Node A[10*MAX_N];

inline void update(int node, int left, int right, int x, int value) {
    if(left == right)
        A[node].leftSum = A[node].rightSum = A[node].totalSum = A[node].ans = value;
    else {
        int m = (left + right)/2;
        if(x <= m)
            update(2*node, left, m, x, value);
        if(x > m)
            update(2*node + 1, m + 1, right, x, value);
        A[node].leftSum = max(A[2*node].leftSum, A[2*node].totalSum + A[2*node + 1].leftSum);
        A[node].rightSum = max(A[2*node + 1].rightSum, A[2*node + 1].totalSum + A[2*node].rightSum);
        A[node].totalSum = A[2*node].totalSum + A[2*node + 1].totalSum;
        A[node].ans = max(max(A[2*node].ans, A[2*node + 1].ans), A[2*node + 1].leftSum + A[2*node].rightSum);
    }
}

inline Node query(int node, int left, int right, int x, int y) {
    if(x <= left && right <= y)
        return A[node];
    else {
        int m = (left + right)/2;
        Node temp1, temp2, temp3;
        if(x <= m)
            temp1 = query(2*node, left, m, x, y);
        if(y > m)
            temp2 = query(2*node + 1, m + 1, right, x, y);
        if(x <= m && y > m) {
            Node temp;
            temp.totalSum = temp1.totalSum + temp2.totalSum;
            temp.leftSum = max(temp1.leftSum, temp1.totalSum + temp2.leftSum);
            temp.rightSum = max(temp2.rightSum, temp2.totalSum + temp1.rightSum);
            temp.ans = max(temp1.ans, temp2.ans);
            temp.ans = max(temp.ans, temp2.leftSum + temp1.rightSum);

            return temp;
        }
        else if(x <= m)
            return temp1;
        else return temp2;
    }
}


int main() {
    ifstream f("sequencequery.in");
    ofstream g("sequencequery.out");

    f >> N >> M;
    for(int i = 1, x; i <= N; ++i) {
        f >> x;
        update(1, 1, N, i, x);
    }


    for(int i = 1, x, y; i <= M; ++i) {
        f >> x >> y;
        g << query(1, 1, N, x, y).ans << "\n";
    }

    f.close();
    g.close();

    return 0;
}