#include <fstream>
#define int long long
using namespace std;
ifstream cin("sequencequery.in");
ofstream cout("sequencequery.out");
const int MAXN=100005;
const int INF=-100000007;
int v[MAXN];
struct nod{
int maxint;
int maxst, maxdr;
int sumint;
};
nod tree[MAXN*4];
struct AINT{
AINT() {
tree[0]={INF, INF, INF, 0};
}
nod merge(nod a, nod b){
int maxx=a.maxdr+b.maxst;
maxx=max(maxx, a.maxint);
maxx=max(maxx, b.maxint);
nod r;
r.maxint=maxx;
r.maxst=a.maxst;
r.sumint=a.sumint+b.sumint;
if(a.sumint+b.maxst>=a.maxst){
r.maxst=a.sumint+b.maxst;
}
r.maxdr=b.maxdr;
if(b.sumint+a.maxdr>=b.maxdr){
r.maxdr=b.sumint+a.maxdr;
}
return r;
}
void init(int node, int st, int dr){
if(st==dr){
nod x;
x.maxint=v[st];
x.maxst=v[st];
x.maxdr=v[st];
x.sumint=v[st];
tree[node]=x;
return;
}
int mid=(st+dr)/2;
init(2*node, st, mid);
init(2*node+1, mid+1, dr);
tree[node]=merge(tree[2*node], tree[2*node+1]);
}
nod query(int node, int st, int dr, int l, int r){
if(st>r || dr<l) return tree[0];
if(st>=l && dr<=r){
return tree[node];
}
int mid=(st+dr)/2;
return merge(query(2*node, st, mid, l, r), query(2*node+1, mid+1, dr, l, r));
}
};
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, q;
cin>>n>>q;
for(int i=1; i<=n; i++){
cin>>v[i];
}
AINT aint;
aint.init(1, 1, n);
while(q--){
int l, r;
cin>>l>>r;
nod ans=aint.query(1, 1, n, l, r);
cout<<ans.maxint<<"\n";
}
}