#include <bits/stdc++.h>
#define int long long

using namespace std;

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

struct nod {
    int sum,pref,suf,rez;
};

int n,q;
vector<int> v;
vector<nod> aint;

nod combine(nod st,nod dr) {
    nod rez;
    rez.sum=st.sum+dr.sum;
    rez.pref=max(st.pref,st.sum+dr.pref);
    rez.suf=max(dr.suf,dr.sum+st.suf);
    rez.rez=max({st.rez,dr.rez,st.suf+dr.pref});
    return rez;
}

void build(int ind,int st,int dr) {
    if(st==dr) {
        aint[ind]={v[st],v[st],v[st],v[st]};
        return;
    }
    int mij=(st+dr)/2;
    build(2*ind+1,st,mij);
    build(2*ind+2,mij+1,dr);
    aint[ind]=combine(aint[2*ind+1],aint[2*ind+2]);
}

nod query(int ind,int st,int dr,int l,int r) {
    if(l<=st&&dr<=r) return aint[ind];
    int mij=(st+dr)/2;
    if(r<=mij) return query(2*ind+1,st,mij,l,r);
    if(l>mij) return query(2*ind+2,mij+1,dr,l,r);
    return combine(query(2*ind+1,st,mij,l,r),query(2*ind+2,mij+1,dr,l,r));
}

signed main(){
    ios::sync_with_stdio(false);
    fin.tie(nullptr);
    fout.tie(nullptr);
    fin>>n>>q;
    v.resize(n);
    aint.resize(4*n);
    for(auto &x:v) fin>>x;
    build(0,0,n-1);
    while(q--) {
        int st,dr;
        fin>>st>>dr;
        st--;
        dr--;
        fout<<query(0,0,n-1,st,dr).rez<<'\n';
    }
    return 0;
}