#include <cstdio>
#include <cassert>

#define MAX_N 100001

struct sequence {
    long long sum, sub_max_sum, left_max_sum, right_max_sum;
};

const long long INF = 2000000000;

int n, m;
int v[MAX_N];
sequence aint[MAX_N * 4];
long long ans, sum;

void read() {
    assert(scanf("%d%d", &n, &m) == 2);

    for (int i = 1; i <= n; ++i)
        assert(scanf("%d", &v[i]) == 1);
}

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

void build(int node, int left, int right) {
    if (left == right) {
        aint[node].sum = aint[node].sub_max_sum = aint[node].left_max_sum = aint[node].right_max_sum = v[left];

        return;
    }

    int mid = (left + right) >> 1;
    int left_son = (node << 1);
    int right_son = (node << 1) + 1;

    build(left_son, left, mid);
    build(right_son, mid + 1, right);

    aint[node].sum = aint[left_son].sum + aint[right_son].sum;
    aint[node].left_max_sum = max(aint[left_son].left_max_sum, aint[left_son].sum + aint[right_son].left_max_sum);
    aint[node].right_max_sum = max(aint[right_son].right_max_sum, aint[right_son].sum + aint[left_son].right_max_sum);

    aint[node].sub_max_sum = max(aint[left_son].sub_max_sum, aint[right_son].sub_max_sum);
    aint[node].sub_max_sum = max(aint[node].sub_max_sum, aint[left_son].right_max_sum + aint[right_son].left_max_sum);
}

void query(int node, int left, int right, int a, int b) {
    if (a <= left && right <= b) {
        ans = max(ans, max(aint[node].sub_max_sum, aint[node].left_max_sum + sum));

        sum = max(sum + aint[node].sum, aint[node].right_max_sum);

        return;
    }

    int mid = (left + right) >> 1;
    int left_son = (node << 1);
    int right_son = (node << 1) + 1;

    if (a <= mid)
        query(left_son, left, mid, a, b);

    if (b > mid)
        query(right_son, mid + 1, right, a, b);
}

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

    read();

    build(1, 1, n);

    while (m) {
        int a, b;
        assert(scanf("%d%d", &a, &b) == 2);

        sum = 0;

        ans = -INF;

        query(1, 1, n, a, b);

        printf("%lld\n", ans);

        --m;
    }
}