#include <bits/stdc++.h>
#define N 800005

using namespace std;
long long sl[N], sr[N], st[N], sm[N], x[200005], sum, sol;
int a, b, n, m, i;
void build (int nod, int l, int r)
{
    if(l == r)
    {
        sl[nod] = sr[nod] = st[nod] = sm[nod] = x[l];
        return;
    }
    int mid = (l + r) / 2;
    build(2 * nod, l, mid);
    build(2 * nod + 1, mid + 1, r);
    sl[nod] = max(st[2 * nod] + sl[2 * nod + 1], sl[2 * nod]);
    sr[nod] = max(st[2 * nod + 1] + sr[2 * nod], sr[2 * nod + 1]);
    st[nod] = st[2 * nod] + st[2 * nod + 1];
    sm[nod] = max(max(sm[2 * nod], sm[2 * nod + 1]), sr[2 * nod] + sl[2 * nod + 1]);
}
void query(int nod, int l, int r)
{
    if(a > r || b < l)
        return;
    if(a <= l && r <= b)
    {
        if(sum < 0)
            sum = 0;
        sol = max(sol, max(sum + sl[nod], sm[nod]));
        sum = max(sum + st[nod], sr[nod]);
        return;
    }

    int mid = (l + r) / 2;
    query(2 * nod, l, mid),
    query(2 * nod + 1, mid + 1, r);
}
int main()
{
    freopen("sequencequery.in", "r", stdin);
    freopen("sequencequery.out", "w", stdout);
    scanf("%d%d", &n, &m);
    for(i = 1; i <= n; i++)
        scanf("%lld", &x[i]);
    build(1, 1, n);
    for(; m; m--)
    {
        scanf("%d%d", &a, &b);
        sol = -(1ll << 60);
        sum=0;
        query(1, 1, n);
        printf("%lld\n", sol );
    }
    return 0;
}