using namespace std;

#include <cstdio>
#include <algorithm>
#include <cassert>

#define FIN "sequencequery.in"
#define FOUT "sequencequery.out"
#define NMAX 1<<17
#define max(a, b) ((a) > (b) ? (a) : (b))
#define INF 0x3f3f3f3f

int N, M, v[NMAX], A[NMAX<<1], B[NMAX<<1], C[NMAX<<1], S[NMAX<<1];

#define mj ((st + dr)>>1)
#define ns (nod<<1)
#define nr (ns + 1)

void build (int nod, int st, int dr)
{
    if (st == dr)
    {
        A[nod] = B[nod] = C[nod] = v[st];
        S[nod] = v[st];
    }
    else
    {
        build (ns, st, mj);
        build (nr, mj + 1, dr);

        A[nod] = max (A[ns], S[ns] + A[nr]);
        B[nod] = max (B[nr], S[nr] + B[ns]);
        C[nod] = max (max (C[nr], C[ns]), A[nr] + B[ns]);

        S[nod] = S[nr] + S[ns];
    }
}

void read ()
{
    scanf ("%d %d\n", &N, &M);

    for (int i = 1; i <= N; ++ i)
        scanf ("%d ", v + i);

    build (1, 1, N);
}

void update (int nod, int st, int dr, int p, int x)
{
    if (st == dr)
    {
        v[st] = x;
        A[nod] = B[nod] = C[nod] = x;
        S[nod] = x;
    }
    else
    {
        if (p <= mj)
            update (ns, st, mj, p, x);
        else
            update (nr, mj + 1, dr, p, x);

        A[nod] = max (A[ns], S[ns] + A[nr]);
        B[nod] = max (B[nr], S[nr] + B[ns]);
        C[nod] = max (max (C[nr], C[ns]), A[nr] + B[ns]);

        S[nod] = S[nr] + S[ns];
    }
}

long long sol, Sum;

void query (int nod, int st, int dr, int a, int b)
{
    if (a <= st && dr <= b)
    {
        sol = max (sol, max (Sum + A[nod], C[nod]));
        Sum = max (Sum + S[nod], B[nod]);
    }
    else
    {
        if (a <= mj)
            query (ns, st, mj, a, b);
        if (b > mj)
            query (nr, mj + 1, dr, a, b);
    }
}

void solve ()
{
    int a, b;
    while (M--)
    {
        sol = Sum = -INF;
        scanf ("%d %d\n", &a, &b);
        
        query (1, 1, N, a, b);
        printf ("%lld\n", sol);
    }
}

int
 main ()
{
    freopen (FIN, "rt", stdin);
    freopen (FOUT, "wt", stdout);

    read ();
    solve ();

    return 0;
}