#include <fstream>
#include <iostream>

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

const int NMAX = 100000;
const long long INF = 1LL<<50;

struct Node {
    long long ssm, sum, prefix, sufix;
};

Node aint[1 + 4 * NMAX];
int v[1 + NMAX];
long long sum, ans;

void merge ( int p ) {
    aint[p].sum = aint[p * 2].sum + aint[p * 2 + 1].sum;
    aint[p].ssm = std:: max ( std::max ( aint[p * 2].ssm, aint[p * 2 + 1].ssm ), aint[p * 2].sufix + aint[p * 2 + 1].prefix );
    aint[p].prefix = std::max ( aint[p * 2].prefix, aint[p * 2].sum + aint[p * 2 + 1].prefix );
    aint[p].sufix = std::max ( aint[p * 2 + 1].sufix, aint[p * 2 + 1].sum + aint[p * 2].sufix );
}

void build ( int p, int left, int right ) {
    if ( left == right ) {
        aint[p].ssm = aint[p].sum = aint[p].sufix = aint[p].prefix = v[left];
        return ;
    }
    int mid = ( left + right ) / 2;
    build ( p * 2 , left, mid );
    build ( p * 2 + 1, mid + 1, right );
    merge ( p );
}

void query ( int p, int left, int right, int b, int e ) {
    if ( b <= left && right <= e ) {
        ans = std::max ( ans, std::max ( sum + aint[p].prefix, aint[p].ssm ) );
        sum = std::max ( sum + aint[p].sum, aint[p].sufix );
        return ;
    }

    int mid = ( left + right ) / 2;
    if ( b <= mid )
        query ( p * 2, left, mid, b, e );
    if ( mid < e )
        query ( p * 2 + 1, mid + 1, right, b, e );
}

int main() {
    int N, Q;

    fin >> N >> Q;

    for ( int i = 1; i <= N; ++i )
        fin >> v[i];
    build ( 1, 1, N );

    for ( int i = 1; i <= Q; ++i ) {
        int x, y;
        fin >> x >> y;
        ans = -INF;
        sum = 0;
        query ( 1, 1, N, x, y );
        fout << ans << '\n';
    }

    fin.close();
    fout.close();

    return 0;
}