#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstring>
#include<set>
#include<map>
#include<cmath>
#include<climits>
using namespace std ;

#define maxn 100001

struct aaa
{
    long long stanga, dreapta, suma, sol ;
};

int N, M ;

int x, y ;

long long rez, curent ;

aaa arbore[3 * maxn] ;

void modifica(int nod, int st, int dr, int poz, int val)
{
    if( st == dr )
        arbore[nod].stanga = arbore[nod].dreapta = arbore[nod].suma = arbore[nod].sol = val ;
    else
    {
        int mij = ( st + dr ) >> 1 ;
        int fiust = 2 * nod ;
        int fiudr = 2 * nod + 1 ;

        if( poz <= mij )
            modifica( fiust, st, mij, poz, val ) ;
        else
            modifica( fiudr, mij + 1, dr, poz, val ) ;

        arbore[nod].stanga = max( arbore[fiust].stanga, arbore[fiudr].stanga + arbore[fiust].suma ) ;
        arbore[nod].dreapta = max( arbore[fiudr].dreapta, arbore[fiust].dreapta + arbore[fiudr].suma ) ;
        arbore[nod].sol = max( max( arbore[fiust].sol, arbore[fiudr].sol ), arbore[fiust].dreapta + arbore[fiudr].stanga ) ;
        arbore[nod].suma = arbore[fiust].suma + arbore[fiudr].suma ;
    }
}

void query(int nod, int st, int dr)
{
    if( x <= st && dr <= y )
    {
        rez = max( rez, max( curent + arbore[nod].stanga, arbore[nod].sol ) ) ;
        curent = max( curent + arbore[nod].suma, arbore[nod].dreapta ) ;
        return ;
    }
    else
    {
        int mij = ( st + dr ) >> 1 ;
        int fiust = 2 * nod ;
        int fiudr = 2 * nod + 1 ;

        if( x <= mij )
            query( fiust, st, mij ) ;
        if( y > mij )
            query( fiudr, mij + 1, dr ) ;
    }
}

int main()
{
	std::ios_base::sync_with_stdio(false) ;

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

    cin >> N >> M ;

    for(int i = 1; i <= N; ++i)
    {
        cin >> x ;
        modifica( 1, 1, N, i, x ) ;
    }

    for(int i = 1; i <= M; ++i)
    {
        cin >> x >> y ;
        rez = LLONG_MIN ;
        curent = 0 ;

        query( 1, 1, N ) ;

        cout << rez << "\n" ;
    }

	return 0 ;
}