#include <fstream>

#define N 200001

using namespace std;

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

const long long inf = 1000000000000ll;
struct arbore{
    long long smax, suma, sst, sdr;
}ait[3 * N];
int v[N], poz, val, a, b;
long long S, ans;

void compare ( int node ){
    ait[node].suma = ait[2 * node].suma + ait[2 * node + 1].suma;
    ait[node].smax = max ( max ( ait[2 * node].smax, ait[2 * node + 1].smax ), ait[2 * node].sdr + ait[2 * node + 1].sst );
    ait[node].sst = max ( ait[2 * node].sst, ait[2 * node].suma + ait[2 * node + 1].sst );
    ait[node].sdr = max ( ait[2 * node + 1].sdr, ait[2 * node + 1].suma + ait[2 * node].sdr );
}

void give_value ( arbore &a, int val ){
    a.smax = a.sst = a.sdr = val;
    a.suma = val;
}

void build ( int node, int st, int dr ){
    if ( st == dr ){
        give_value ( ait[node], v[st] );
        return;
    }
    int mid = ( st + dr ) >> 1;
    build ( 2 * node, st, mid );
    build ( 2 * node + 1, mid + 1, dr );
    compare ( node );
}

void quary ( int node, int st, int dr ){
    if ( a <= st && dr <= b ){
        ans = max ( ans, max ( S + ait[node].sst, ait[node].smax ) );
        S = max ( S + ait[node].suma, ait[node].sdr );
        return;
    }
    int mid = ( st + dr ) >> 1;
    if ( a <= mid )
        quary ( 2 * node, st, mid );
    if ( mid + 1 <= b )
        quary ( 2 * node + 1, mid + 1, dr );
}

int main()
{   int n, i, m, op;
    f >> n >> m;
    for ( i = 1; i <= n; i++ )
        f >> v[i];
    build ( 1, 1, n );
    for ( i = 1; i <= m; i++ ){
        f >> a >> b;
        ans = -inf;
        S = 0;
        quary ( 1, 1, n );
        g << ans << '\n';
    }
    return 0;
}