#include <cstdio>
#include <algorithm>
using namespace std;

struct segment_tree {

    long long sum, best, left, right;

};
const long long INFI = 2e18;
const int NMAX = 100003;

segment_tree AINT[NMAX * 3];
long long best, S;
int V[NMAX], _left, _right;

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

    if (left == right) {
        AINT[node].sum = AINT[node].best = AINT[node].left = AINT[node].right = V[left];
        return;
    }
    const int &middle = left + right >> 1;
    AINT_build (node * 2, left, middle);
    AINT_build (node * 2 + 1, middle + 1, right);
    AINT[node].sum = AINT[node * 2].sum + AINT[node * 2 + 1].sum;
    AINT[node].best = max (max (AINT[node * 2].best, AINT[node * 2 + 1].best), AINT[node * 2].right + AINT[node * 2 + 1].left);
    AINT[node].left = max (AINT[node * 2].left, AINT[node * 2].sum + AINT[node * 2 + 1].left);
    AINT[node].right = max (AINT[node * 2 + 1].right, AINT[node * 2 + 1].sum + AINT[node * 2].right);

}

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

    if (_right < left || _left > right)
        return;
    if (left >= _left && _right >= right) {
        best = max (best, max (AINT[node].best, S + AINT[node].left));
        S = max (S + AINT[node].sum, AINT[node].right);
        return;
    }
    const int &middle = left + right >> 1;
    AINT_query (node * 2, left, middle);
    AINT_query (node * 2 + 1, middle + 1, right);

}

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);
    AINT_build (1, 1, N);
    while (M--) {
        scanf ("%d%d", &_left, &_right);
        best = -INFI;
        S = 0;
        AINT_query (1, 1, N);
        printf ("%lld\n", best);
    }

}