#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];


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) );
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==y) ){
    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);
    }
}
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];}

build_seg(1, 1, n);

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



return 0;
}