#include <bits/stdc++.h>
using namespace std;
ifstream in("sequencequery.in");
ofstream out("sequencequery.out");
const int DIM = 100005;
const long long INF = 1e15;

struct str {
    long long sum, lssm, rssm, ssm; };
str aint[DIM * 4]; int v[DIM];

str updaten( str s1, str s2 ) {
    str s;
    s.sum = s1.sum + s2.sum;
    s.lssm = max( s1.lssm, s1.sum + s2.lssm );
    s.rssm = max( s2.rssm, s2.sum + s1.rssm );
    s.ssm = max( s1.rssm + s2.lssm, max(s1.ssm,s2.ssm));
    return s;
}
void build( int nod ,int st, int dr ){
    if( st == dr ){
        aint[nod] = { v[st], v[st], v[st],v[st]};
        return;
    }
    int mid = ( st + dr )>>1;
    build( nod<<1, st, mid);
    build(nod<<1|1,mid+1,dr);
    
    aint[nod] = updaten( aint[nod << 1], aint[nod << 1 | 1] );
}
str query( int nod, int st, int dr, int x, int y ){
    if( st > y || dr < x ){
        return { 0,-INF,-INF,-INF};
    }
    if( st >= x && dr <= y ){
        return aint[nod];
    }
    int mid = ( st + dr )>>1;
    str stanga = query( nod<<1,st,mid,x,y );
    str dreapta = query( nod<<1|1,mid +1,dr,x,y);
    return updaten( stanga, dreapta );
}
int main(void) {
    int n, m;
    in >> n>> m;
    for( int i = 1; i <= n; i ++ ){
        in >> v[i];
    }
    build(1,1,n);
    for( int i = 1; i <= m; i ++ ){
        int x,y;
        in >> x >> y;
        out<<query( 1,1,n,x,y).ssm<<"\n";
    }
    return 0;
}