#include <iostream>
#include <climits>

#define NMAX 100002

using namespace std;

struct ssm {
    long long pref;
    long long suf;
    long long suma;
    long long maxim;
};

int A[NMAX], N, M, S, E;
long long val, suf;
ssm T[4*NMAX];

void build(int node, int st, int dr) {
    if(st == dr) {
        T[node] = {
            A[st],
            A[st],
            A[st],
            A[st]
        };
    } else {
        int mid = (st + dr) / 2;
        build(2 * node, st, mid);
        build(2 * node + 1, mid + 1, dr);
        T[node] = {
            max(T[2 * node].pref, T[2 * node].suma + T[2 * node + 1].pref),
            max(T[2 * node + 1].suf, T[2 * node + 1].suma + T[2 * node].suf),
            T[2 * node].suma + T[2 * node + 1].suma,
            max(max(T[2 * node].maxim, T[2 * node + 1].maxim), T[2 * node].suf + T[2 * node + 1].pref)
        };
    }
}

void query(int node, int st, int dr) {
    if(S <= st && dr <= E) {
        val = max(val, max(T[node].maxim, T[node].pref + suf));
        suf = max(suf + T[node].suma, T[node].suf);
    } else {
        int mid = (st + dr) / 2;
        if(S <= mid) {
            query(node * 2, st, mid);
        }
        if(E > mid) {
            query(node * 2  + 1, mid + 1, dr);
        }
    }

}

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

    cin >> N >> M;

    for(int i = 1; i <= N; i++) {
        cin >> A[i];
    }

    build(1, 1, N);

    for(int i = 1; i <= M; i++) {
        cin >> S >> E;
        val = LLONG_MIN;
        suf = 0;
        query(1, 1, N);
        cout << val << "\n";
    }


    return 0;
}