#include <iostream>
#include <cstdio>

#define NMax 200005

using namespace std;

typedef struct
{
    long long S;
    long long L;
    long long R;
    long long M;
}
ArbInt;

ArbInt AI[4*NMax];
int N;

inline long long Max (long long a, long long b)
{
    if (a>b)
    {
        return a;
    }
    return b;
}

inline void Reunite (ArbInt &A, ArbInt AL, ArbInt AR)
{
    A.S=AL.S+AR.S;
    A.L=Max (AL.L, AL.S+AR.L);
    A.R=Max (AR.R, AR.S+AL.R);
    A.M=Max (Max (AL.M, AR.M), AL.R+AR.L);
}

void Update (int K, int L, int R, int P, long long V)
{
    int Mid=(L+R)/2;
    if (L==R)
    {
        AI[K].S=AI[K].L=AI[K].R=AI[K].M=V;
        return;
    }
    if (P<=Mid)
    {
        Update (2*K, L, Mid, P, V);
    }
    else
    {
        Update (2*K+1, Mid+1, R, P, V);
    }
    Reunite (AI[K], AI[2*K], AI[2*K+1]);
}

ArbInt Query (int K, int L, int R, int QL, int QR)
{
    int Mid=(L+R)/2;
    if (L==QL and R==QR)
    {
        return AI[K];
    }
    if (QR<=Mid)
    {
        return Query (2*K, L, Mid, QL, QR);
    }
    if (QL>Mid)
    {
        return Query (2*K+1, Mid+1, R, QL, QR);
    }
    ArbInt Q1=Query (2*K, L, Mid, QL, Mid);
    ArbInt Q2=Query (2*K+1, Mid+1, R, Mid+1, QR);
    ArbInt Q;
    Reunite (Q, Q1, Q2);
    return Q;
}

int main()
{
    freopen ("sequencequery.in", "r", stdin);
    freopen ("sequencequery.out", "w", stdout);
    int NQ;
    scanf ("%d %d", &N, &NQ);
    for (int i=1; i<=N; ++i)
    {
        int X;
        scanf ("%d", &X);
        Update (1, 1, N, i, (long long)X);
    }
    for (; NQ>0; --NQ)
    {
        int X, Y;
        scanf ("%d %d", &X, &Y);
        ArbInt Q=Query (1, 1, N, X, Y);
        printf ("%lld\n", Q.M);
    }
    return 0;
}