# include <bits/stdc++.h>
# define ll long long

using namespace std;

const int inf = 0x3f3f3f3f, Nmax = 1e5 + 5;

struct aint{ll tot, best, st, dr;};

aint arb[3 * Nmax];
ll ans, s;

int a[Nmax], n, m, i;

void build (int node, int left, int right) {
    if (left == right) {
        arb[node].st = arb[node].dr = arb[node].best = arb[node].tot = a[left];
        return;
    }

    int mid = (left + right) >> 1;

    build (node * 2, left, mid);
    build (node * 2 + 1, mid + 1, right);

    arb[node].tot = arb[node * 2].tot + arb[node * 2 + 1].tot;
    arb[node].best = max( max(arb[node * 2].best, arb[node * 2 + 1].best), arb[node * 2].dr + arb[node * 2 + 1].st );
    arb[node].st = max(arb[node * 2].st, arb[node * 2].tot + arb[node * 2 + 1].st);
    arb[node].dr = max(arb[node * 2 + 1].dr, arb[node * 2 + 1].tot + arb[node * 2].dr);
}

void query(int node, int left, int right, int x, int y) {
    if (x <= left && right <= y) {
        ans = max(ans, max(arb[node].best, arb[node].st + s));
        s = max(arb[node].dr, arb[node].tot + s);
        return;
    }

    int mid = (left + right) >> 1;

    if (x <= mid) query(node * 2, left, mid, x, y);
    if (y > mid) query(node * 2 + 1, mid + 1, right, x, y);

}

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

    scanf("%d %d\n", &n, &m);

    for (i = 1; i <= n; ++i)
        scanf("%d ", &a[i]);

    build(1, 1, n);

    for (i = 1; i <= m; ++i){
        int x, y;
        scanf("%d %d\n", &x, &y);
        ans = s = -inf;
        query (1, 1, n, x, y);
        printf("%lld\n", ans);
    }

    return 0;
}