#include <bits/stdc++.h>

using namespace std;

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

#define int long long

int pref[400001];
int suf[400001];
int best[400001];
int total[400001];
int v[100001];

void imbinare ( int nod )
{
    pref[nod] = max ( pref[nod * 2], total[nod * 2] + pref[nod * 2 + 1] );
    suf[nod] = max ( suf[nod * 2 + 1], total[nod * 2 + 1] + suf[nod * 2] );
    best[nod] = max ( max ( best[nod * 2], best[nod * 2 + 1] ), suf[nod * 2] + pref[nod * 2 + 1] );
    total[nod] = total[nod * 2] + total[nod * 2 + 1];
}

void build ( int nod, int st, int dr )
{
    if ( st == dr )
    {
        pref[nod] = v[st];
        suf[nod] = v[st];
        best[nod] = v[st];
        total[nod] = v[st];
        return;
    }
    int mij = ( st + dr ) / 2;
    build ( nod * 2, st, mij );
    build ( nod * 2 + 1, mij + 1, dr );
    imbinare ( nod );
}

int sol;

void query ( int nod, int st, int dr, int &a, int &b )
{
    if ( dr < a || st > b )
        return;
    if ( a == st && dr <= b )
    {
        sol = max ( sol, max ( best[nod], suf[0] + pref[nod] ) );
        suf[0] = max ( suf[0] + total[nod], suf[nod] );
        total[0] += total[nod];
        a = dr + 1;
        return;
    }
    int mij = ( st + dr ) / 2;
    query ( nod * 2, st, mij, a, b );
    query ( nod * 2 + 1, mij + 1, dr, a, b );
}

signed main()
{
    int n, q;
    f >> n >> q;
    for ( int i = 1; i <= n; i ++ )
        f >> v[i];
    build ( 1, 1, n );
    while ( q -- )
    {
        int st, dr;
        f >> st >> dr;
        sol = INT_MIN;
        total[0] = suf[0] = 0;
        query ( 1, 1, n, st, dr );
        g << sol << '\n';
    }
    return 0;
}