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

using namespace std;
long long sol[N], x[100005], mini[N], maxi[N], minp;
int a, b, n, m, i;
void build (int nod, int l, int r)
{
    if(l == r)
    {
        sol[nod] = x[l] - x[l - 1];
        maxi[nod] = mini[nod] = x[l];
        return;
    }
    int mid = (l + r) / 2;
    build(2 * nod, l, mid);
    build(2 * nod + 1, mid + 1, r);
    mini[nod] = min(mini[2 * nod], mini[2 * nod + 1]);
    maxi[nod] = max(maxi[2 * nod], maxi[2 * nod + 1]);
    sol[nod] = max(max(sol[2 * nod], sol[2 * nod + 1]), maxi[2 * nod + 1] - mini[2 * nod]);
}
long long query(int nod, int l, int r)
{
    if(a > r || b < l)
        return -(1ll << 60);
    if(a <= l && r <= b)
    {
        long long ret =sol[nod];
        if(minp != (1ll << 60))
            ret = max(ret, maxi[nod] - minp);
        minp = min(mini[nod], minp);
        return ret;
    }

    int mid = (l + r) / 2;
    long long soll = query(2 * nod, l, mid), solr = query(2 * nod + 1, mid + 1, r);
    return max(soll, solr);
}
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]);
        x[i] += x[i - 1];
    }
    build(1, 1, n);
    for(; m; m--)
    {
        scanf("%d%d", &a, &b);
        minp = 1ll << 60;
        printf("%lld\n", query(1, 1, n));
    }
    return 0;
}