#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;

#define Nmax 100010
#define LeftSon (2 * Node)
#define RightSon (2 * Node + 1)

struct Segtree
{
    long long Lsub, Rsub, Sum, Best;
}Aint[4 * Nmax];

int N, V[Nmax], M, X, Y;
long long Ans, AntSum;

void Build(int Node, int Left, int Right)
{
    if(Left == Right)
    {
        Aint[Node].Lsub = Aint[Node].Rsub = Aint[Node].Sum = Aint[Node].Best = V[Left];
        return ;
    }
    int Mid = (Left + Right) / 2;

    Build(LeftSon, Left, Mid);
    Build(RightSon, Mid + 1, Right);

    Aint[Node].Lsub = max(Aint[LeftSon].Lsub, Aint[LeftSon].Sum + Aint[RightSon].Lsub);
    Aint[Node].Rsub = max(Aint[RightSon].Rsub, Aint[RightSon].Sum + Aint[LeftSon].Rsub);
    Aint[Node].Best = max(max(Aint[LeftSon].Best, Aint[RightSon].Best), Aint[LeftSon].Rsub + Aint[RightSon].Lsub);
    Aint[Node].Sum = Aint[LeftSon].Sum + Aint[RightSon].Sum;
}

void Query(int Node, int Left, int Right, int LeftBound, int RightBound)
{
    if(LeftBound <= Left && Right <= RightBound)
    {
        AntSum = max(AntSum, 0LL);
        Ans = max(Ans, max(Aint[Node].Best, AntSum + Aint[Node].Lsub));
        AntSum = max(AntSum + Aint[Node].Sum, Aint[Node].Rsub);
        return ;
    }
    int Mid = (Left + Right) / 2;
    if(LeftBound <= Mid) Query(LeftSon, Left, Mid, LeftBound, RightBound);
    if(Mid < RightBound) Query(RightSon, Mid + 1, Right, LeftBound, RightBound);
}

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

    scanf("%i %i", &N, &M);
    for(int i = 1; i <= N; ++ i) scanf("%i", &V[i]);

    Build(1, 1, N);

    for(int i = 1; i <= M; ++ i)
    {
        scanf("%i %i", &X, &Y);
        AntSum = 0;
        Ans = -(1LL << 60);

        Query(1, 1, N, X, Y);
        printf("%lld\n", Ans);
    }
    return 0;
}