#include <iostream>
#include <fstream>

using namespace std;

const int Nmax = 100005;

struct node
{
    int totalSum;
    int bestPreffix;
    int bestSuffix;
    int bestSum;
};

node Arb[8 * Nmax];

void update( int nod, int st, int dr, int val, int pos )
{
    if ( st == dr )
    {
        Arb[nod].totalSum = val;
        Arb[nod].bestPreffix = val;
        Arb[nod].bestSuffix = val;
        Arb[nod].bestSum = val;
    }
    else
    {
        int m = ( st + dr ) / 2;

        if ( pos <= m )
                update( 2 * nod, st, m, val, pos );
        else
                update( 2 * nod + 1, m + 1, dr, val, pos );

        Arb[nod].totalSum = Arb[2 * nod].totalSum + Arb[2 * nod + 1].totalSum;
        Arb[nod].bestPreffix = max( Arb[2 * nod].bestPreffix, Arb[2 * nod].totalSum + Arb[2 * nod + 1].bestPreffix );
        Arb[nod].bestSuffix = max( Arb[2 * nod + 1].bestSuffix, Arb[2 * nod + 1].totalSum + Arb[2 * nod].bestSuffix );
        Arb[nod].bestSum = max( Arb[2 * nod].bestSum, Arb[2 * nod + 1].bestSum );
        Arb[nod].bestSum = max( Arb[nod].bestSum, Arb[2 * nod].bestSuffix + Arb[2 * nod + 1].bestPreffix );
    }
}

node query( int nod, int st, int dr, int start, int finish )
{
    if ( start <= st && dr <= finish )
    {
        return Arb[nod];
    }
    else
    {
        int m = ( st + dr ) / 2;
        int lf = 0, rt = 0;
        node lft, rgt;

        if ( start <= m )
        {
            lf = 1;
            lft = query( 2 * nod, st, m, start, finish );
        }

        if ( m < finish )
        {
            rt = 1;
            rgt = query( 2 * nod + 1, m + 1, dr, start, finish );
        }

        if ( lf + rt != 2 )
        {
            if ( lf )
                    return lft;
            else
                    return rgt;
        }
        else
        {
            node temp;

            temp.totalSum = lft.totalSum + rgt.totalSum;
            temp.bestPreffix = max( lft.bestPreffix, lft.totalSum + rgt.bestPreffix );
            temp.bestSuffix = max( rgt.bestSuffix, rgt.totalSum + lft.bestSuffix );
            temp.bestSum = max( max ( lft.bestSum, rgt.bestSum ), lft.bestSuffix + rgt.bestPreffix );

            return temp;
        }
    }
}

int main()
{
    ifstream f("sequencequery.in");
    ofstream g("sequencequery.out");

    int N, M;

    f >> N >> M;

    for ( int i = 1, val; i <= N; ++i )
    {
        f >> val;
        update( 1, 1, N, val, i );
    }

    for ( int i = 1, x, y; i <= M; ++i )
    {
        f >> x >> y;

        node temp = query( 1, 1, N, x, y );

        g << temp.bestSum << "\n";
    }

    return 0;
}