#include <cstdio>
#include <cassert>

struct elem {
    long long sum, leftsum, rightsum, ans;
};

const int kMaxN = 100005, INF = 0x3f3f3f3f;

int N, Q;

elem sol, itree[4 * kMaxN];

inline long long max(long long x, long long y) {
    return x > y ? x : y;
}

void recompute(elem &A, elem B, elem C) {
    A.sum = B.sum + C.sum;
    A.leftsum = max(B.leftsum, B.sum + C.leftsum);
    A.rightsum = max(C.rightsum, B.rightsum + C.sum);
    A.ans = max(B.rightsum + C.leftsum, max(B.ans, C.ans));
}

inline void update(int node, int S, int E, int pos, int value) {
    if (S == E) {
        itree[node].sum = value;
        itree[node].leftsum = value;
        itree[node].rightsum = value;
        itree[node].ans = value;
        return;
    }

    int M = (S + E) / 2;

    if (pos <= M)
        update(2 * node, S, M, pos, value);
    else
        update(2 * node + 1, M + 1, E, pos, value);

    recompute(itree[node], itree[2 * node], itree[2 * node + 1]);
}

inline void reset(elem &A) {
    A.sum = A.leftsum = A.rightsum = 0;
    A.ans = -INF;
}

inline void query(int node, int S, int E, int x, int y) {
    if (E < x || y < S)
        return;

    if (x <= S && E <= y) {
        recompute(sol, sol, itree[node]);
        return;
    }

    int M = (S + E) / 2;

    query(2 * node, S, M, x, y);
    query(2 * node + 1, M + 1, E, x, y);
}

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

    assert(scanf("%d%d", &N, &Q) == 2);

    for (int i = 1; i <= N; ++i) {
        int x;
        assert(scanf("%d", &x));
        update(1, 1, N, i, x);
    }

    for (int i = 1; i <= Q; ++i) {
        int x, y;
        assert(scanf("%d%d", &x, &y) == 2);
        reset(sol);
        query(1, 1, N, x, y);
        printf("%lld\n", sol.ans);
    }

    return 0;
}