#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <deque>

#define INF ( (1 << 30) - 1 + (1 << 30) )
#define mod 666013

using namespace std;
typedef long long LL;

struct aintNod
{
    LL pfx, sfx, sum, bst;
}rez, aint[600005];
LL n, i, m, op, x, y;
LL v[200005];

aintNod C(aintNod a, aintNod b)
{
    aintNod rez;

    rez.sum = a.sum + b.sum;
    rez.pfx = max(a.pfx, a.sum + b.pfx);
    rez.sfx = max(b.sfx, b.sum + a.sfx);
    rez.bst = max( max(a.bst, b.bst) , a.sfx +  b.pfx);

    return rez;
}

void B(LL nod, LL st, LL dr)
{
    if(st == dr)
    {
        aint[nod].pfx = aint[nod].sfx = aint[nod].sum = aint[nod].bst = v[st];
        return;
    }

    LL mij = st + ( (dr - st) >> 1 );

    B( nod * 2, st, mij );
    B( nod * 2 + 1, mij + 1, dr );

    aint[nod] = C( aint[nod * 2], aint[nod * 2 + 1] );
}

void Q(LL nod, LL st, LL dr, LL sti, LL dri)
{
    if(sti <= st && dr <= dri)
    {
        rez = C(rez, aint[nod]);
        return;
    }

    LL mij = st + ( (dr - st) >> 1 );
    if(sti <= mij)
        Q(nod * 2, st, mij, sti, dri);
    if(mij < dri)
        Q(nod * 2 + 1, mij + 1, dr, sti, dri);
}

int main()
{
    freopen("sequencequery.in", "r", stdin);
    freopen("sequencequery.out", "w", stdout);
    scanf("%lld%lld", &n, &m);
    for(i = 1; i <= n; i++)
        scanf("%lld", &v[i]);
    B(1, 1, n);
    while(m--)
    {
        scanf("%lld%lld",&x, &y);
        rez.sum = 0;
        rez.bst = rez.pfx = rez.sfx = -20000000;
        Q(1, 1, n, x, y);
        printf("%lld\n", rez.bst);
    }
    return 0;
}