#include<bits/stdc++.h>
using namespace std;
#define INIT  ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define mp make_pair
#define pb push_back
#define ft first
#define sc second
#define ll long long
#define pii pair<int, int>
#define count_bits __builtin_popcount
#define int ll


ifstream fin("sequencequery.in"); ofstream fout("sequencequery.out");
#define cin fin
#define cout fout

int n, m;
int p[100010], a[100010];

struct node{
int l, r, mx, cmp;
};
node seg[400010];

/*int rmq1[100010][18], //maximuri
rmq2[100010][18]; //minimuri
int power[100010];

void build_rmq1(){
    for(int i=1; (1ll<<i)<=n; i++){
        for(int j=0; (j+(1ll<<i)-1)<=n; j++){
            rmq1[j][i]=max(rmq1[j][i-1], rmq1[j+(1ll<<(i-1))][i-1]);
        }
    }
}

void build_rmq2(){
    for(int i=1; (1ll<<i)<=n; i++){
        for(int j=0; (j+(1ll<<i)-1)<=n; j++){
            rmq2[j][i]=min(rmq2[j][i-1], rmq2[j+(1ll<<(i-1))][i-1]);
        }
    }
}

void build_power(){
int lg=0;
for(int i=1; i<=(n+1); i++){
    if( (1ll<<(lg+1) )<=i){lg++;}
    power[i]=lg;
}
}


int get_min(int x, int y){
int lg=power[y-x+1];
return min(rmq2[x][lg], rmq2[y-(1ll<<lg)+1][lg]);
}

int get_max(int x, int y){
int lg=power[y-x+1];
return max(rmq1[x][lg], rmq1[y-(1ll<<lg)+1][lg]);
}
*/

void build_seg(int nod, int tl, int tr){
int med=(tl+tr)/2;
if(tl==tr){
    seg[nod].l=a[med]; seg[nod].r=a[med]; seg[nod].mx=a[med];seg[nod].cmp=a[med]; return;
}
build_seg(nod*2, tl, med); build_seg(2*nod+1, med+1, tr);
seg[nod].l=max(seg[2*nod].cmp+max(0ll, seg[2*nod+1].l), seg[2*nod].l);
seg[nod].r=max(max(0ll, seg[2*nod].r)+seg[2*nod+1].cmp, seg[2*nod+1].r);
seg[nod].mx=max(max(seg[2*nod].r+seg[2*nod+1].l, max(seg[2*nod].mx, seg[2*nod+1].mx) ), max(seg[nod].r, seg[nod].l) );
//cout<<seg[nod].l<<" "<<seg[nod].mx<<" "<<seg[nod].r<<" || "<<tl<<" "<<tr<<"\n";
seg[nod].cmp=(p[tr]-p[tl-1]);
}


int err=1e11;
node query(int nod, int tl, int tr, int x, int y){
node res;
if( (tl>y) || (tr<x) ){
    res.mx=err; return res;
}

int med=(tl+tr)/2;
if( (tl==x) && (tr==x) ){
    res.mx=seg[nod].mx; res.l=seg[nod].l; res.r=seg[nod].r; res.cmp=seg[nod].cmp; return res;
}
node res1=query(nod*2, tl, med, x, min(y, med)), res2=query(2*nod+1, (med+1), tr, max(x, (med+1)), y );



if(res1.mx==err){
    res.l=res2.l; res.r=res2.r; res.cmp=res2.cmp;
    res.mx=max(max(res.l, res.r), res2.mx);
    res.cmp=res2.cmp;
}
else{
    if(res2.mx==err){
            res.l=res1.l; res.r=res1.r; res.cmp=res1.cmp;
        res.mx=max(max(res.l, res.r), res1.mx);
        res.cmp=res1.cmp;
    }
    else{
        res.l=max(res1.cmp+max(res2.l, 0ll), res1.l); res.r=max(res2.r, max(res1.r, 0ll)+res2.cmp);
        res.mx=max(max(res.l, res.r), max( max(res1.mx, res2.mx), res1.r+res2.l) );
        res.cmp=(res1.cmp+res2.cmp);
    }
}
//cout<<res.l<<" "<<res.mx<<" "<<res.r<<" x||x "<<x<<" "<<y<<"\n";
return res;
}



int32_t main(){
INIT
cin>>n>>m;
for(int i=1; i<=n; i++){cin>>a[i]; p[i]=p[i-1]+a[i]; /*rmq1[i][0]=p[i]; rmq2[i][0]=p[i];*/ }
/*build_rmq1();
build_rmq2();
build_power();*/
build_seg(1, 1, n);

while(m--){
    int x, y; cin>>x>>y;
    cout<<(query(1, 1, n, x, y).mx)<<"\n";
}



return 0;
}