#include <cstdio>
#include <algorithm>
#define l first
#define r second
using namespace std;

const int NMAX = 100003, INFI = 2e9;

pair <int, int> AIB[NMAX * 3];
long long S[NMAX], s, best;
int V[NMAX], _left, _right, last_i;
bool first_time;

void AIB_query (const int &node, const int &left, const int &right) {

    if (left >= _left && right <= _right) {
        if (first_time) {
            first_time = 0;
            last_i = AIB[node].r;
            s = S[last_i] - S[AIB[node].l - 1];
            if (s > best)
                best = s;
            return;
        }
        if (s < 0)
            s = 0,
            last_i = AIB[node].l - 1;
        if (S[AIB[node].r] - S[last_i] > S[AIB[node].r] - S[AIB[node].l - 1])
            s += S[AIB[node].r] - S[last_i];
        else
            s = S[AIB[node].r] - S[AIB[node].l - 1];
        if (s > best)
            best = s;
        last_i = AIB[node].r;
        return;
    }
    if (left > _right || right < _left)
        return;
    int middle = left + right >> 1;
    AIB_query (node * 2, left, middle);
    AIB_query (node * 2 + 1, middle + 1, right);

}

void AIB_build (const int &node, const int &left, const int &right) {

    if (left == right) {
        AIB[node] = make_pair (left, left);
        return;
    }
    const int &middle = left + right >> 1;
    AIB_build (node * 2, left, middle);
    AIB_build (node * 2 + 1, middle + 1, right);
    int l = S[AIB[node * 2 + 1].r] - S[AIB[node * 2 + 1].l - 1], r = S[AIB[node * 2].r] - S[AIB[node * 2].l - 1], b = S[AIB[node * 2 + 1].r] - S[AIB[node * 2].l - 1];
    if (b > l && b > r)
        AIB[node] = make_pair (AIB[node * 2].l, AIB[node * 2 + 1].r);
    else
        if (r > l)
            AIB[node] = make_pair (AIB[node * 2].l, AIB[node * 2].r);
        else
            AIB[node] = make_pair (AIB[node * 2 + 1].l, AIB[node * 2 + 1].r);

}

int main () {

    freopen ("sequencequery.in", "r", stdin);
    freopen ("sequencequery.out", "w", stdout);
    int N, M, i;

    scanf ("%d%d", &N, &M);
    for (i = 1; i <= N; ++i)
        scanf ("%d", V + i),
        S[i] = S[i - 1] + V[i];
    AIB_build (1, 1, N);
    while (M--) {
        scanf ("%d%d", &_left, &_right);
        s = 0;
        best = -INFI;
        first_time = 1;
        AIB_query (1, 1, N);
        printf ("%d\n", best);
    }

}