#include <cstdio>
#include <algorithm>

using namespace std;

#define maxn 100010

int q0, m, n, a, b, nod;
struct arb
{
    long long st, dr, tot, best;
} arb[3*maxn];
int q[maxn], v[maxn];
long long sol, cr;

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

    int med=(left+right)/2;

    build(nod*2, left, med);
    build(nod*2+1, med+1, right);

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

void query(int nod, int left, int right, int qleft, int qright)
{
    if(qleft<=left && right<=qright)
    {
        q[++q0]=nod;
        return;
    }

    int med=(left+right)/2;

    if(qleft<=med)
        query(nod*2, left, med, qleft, qright);
    if(med<qright)
        query(nod*2+1, med+1, right, qleft, qright);
}

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

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

    build(1, 1, n);

    while(m--)
    {
        scanf("%d%d", &a, &b);

        q0=0;
        query(1, 1, n, a, b);

        sol=cr=-100000;
        for(int i=1; i<=q0; ++i)
        {
            nod=q[i];
            sol=max(sol, max(arb[nod].best, cr+arb[nod].dr));
            cr=max(cr+arb[nod].tot, arb[nod].st);
        }

        printf("%lld\n", sol);
    }

    return 0;
}