#include <bits/stdc++.h>
#define Nmax 100002
#define INF -(1LL << 60)
#define ll long long
using namespace std;

ifstream fin("sequencequery.in");
ofstream fout("sequencequery.out");

int N, Q, Max;
int v[Nmax];
ll sum[4 * Nmax], le[4 * Nmax], ri[4 * Nmax], bst[4 * Nmax], ans, curr;

void update(int node, int l, int r, int pos, int val) {
    if (l == r)
        le[node] = ri[node] = bst[node] = sum[node] = val;
    else {
        int mid = (l + r) / 2, x = 2 * node, y = 2 * node + 1;
        if (pos <= mid) update(x, l, mid, pos, val);
        else update(y, mid + 1, r, pos, val);

        le[node] = max(le[x], sum[x] + le[y]);
        ri[node] = max(ri[y], ri[x] + sum[y]);
        sum[node] = sum[x] + sum[y];
        bst[node] = max(bst[x], bst[y]);
        bst[node] = max(bst[node], max(sum[node], max(le[node], ri[node])));
    }
}
void query(int node, int l, int r, int a, int b) {
    if (l >= a && r <= b) {
        ans = max(ans, curr + le[node]);
        ans = max(ans, bst[node]);
        curr = max(curr + sum[node], ri[node]);
    }
    else {
        int mid = (l + r) / 2;
        if (a <= mid) query(2 * node, l, mid, a, b);
        if (mid < b) query(2 * node + 1, mid + 1, r, a, b);
    }
}
int main()
{
    fin >> N >> Q;
    for (int i = 1; i <= 4 * N; ++i)
        sum[i] = le[i] = ri[i] = bst[i] = INF;
    for (int i = 1; i <= N; ++i)
        fin >> v[i], update(1, 1, N, i, v[i]);

    while (Q--) {
        int x, y;
        fin >> x >> y;
        ans = INF, curr = 0;
        query(1, 1, N, x, y);
        fout << ans << '\n';
    }

    return 0;
}