#include <fstream>
#include <cstdlib>

#define out -100010

using namespace std;

ifstream fin ("sequencequery.in");
ofstream fout ("sequencequery.out");

// Nod pentru arborele de intervale
typedef struct {
    long long maxseq; // subsecventa de suma maxima
    long long sum; // suma intervalului
    long long lseq; // secventa de suma maxima ce se termina pe ultimul element din interval
    long long fseq; // secventa de suma maxima ce incepe pe primul element din interval
}nod;

nod arbint[4 * 100001];

nod combine ( nod leftSon, nod rightSon ) {

    nod res;
    long long seqComb = leftSon.lseq + rightSon.fseq;

    if ( seqComb > leftSon.maxseq && seqComb > rightSon.maxseq )
        res.maxseq = seqComb;
    else {
        if ( leftSon.maxseq > rightSon.maxseq )
            res.maxseq = leftSon.maxseq;
        else
            res.maxseq = rightSon.maxseq;
    }

    if ( leftSon.lseq + rightSon.sum > rightSon.lseq )
        res.lseq = leftSon.lseq + rightSon.sum;
    else
        res.lseq = rightSon.lseq;

    if ( leftSon.sum + rightSon.fseq > leftSon.fseq )
        res.fseq = leftSon.sum + rightSon.fseq;
    else
        res.fseq = leftSon.fseq;

    res.sum = leftSon.sum + rightSon.sum;

    return res;
}

nod query ( int lo, int hi, int node, int lowerBound, int upperBound ) {

    if ( lo > upperBound || hi < lowerBound ) {
        nod res;
        res.maxseq = res.fseq = res.lseq = res.sum = out;
        return res;
    }

    if ( lo >= lowerBound && hi <= upperBound )
        return arbint[node];

    int mid = lo + (hi-lo)/2;
    nod left = query ( lo, mid, node*2, lowerBound, upperBound);
    nod right = query ( mid+1, hi, node*2+1, lowerBound, upperBound );

    if ( left.maxseq == out )
        return right;
    else if ( right.maxseq == out )
        return left;

    nod res = combine ( left, right );
    return res;
}

void update ( int lo, int hi, int node, int pos, int val) {

    if ( lo == hi ) {
        arbint[node].maxseq = val;
        arbint[node].sum = val;
        arbint[node].lseq = val;
        arbint[node].fseq = val;
        return;
    }

    int mid = lo + (hi-lo)/2;
    if ( mid >= pos )
        update( lo, mid, node*2, pos, val );
    else
        update( mid+1, hi, node*2+1, pos, val );

    arbint[node] = combine( arbint[node*2], arbint[node*2+1] );
}

void solve () {

    int n, m, x, y;
    fin >> n >> m;

    for ( int i = 1; i <= n; i++ ) {
        fin >> x;
        update ( 1, n, 1, i, x );
    }

    while ( m-- ) {
        fin >> x >> y;
        fout << query (1, n, 1, x, y).maxseq << "\n";
    }
}

int main()
{
    solve ();
    return 0;
}