#include <bits/stdc++.h>

using namespace std;
int n,x,a,b,st,dr,sum[400004],Max,start,finish,nod,val,pos,m,pref[400004],suf[400004],sol[400004];
void build(int st,int dr ,int nod){
    if(st==dr) return;
    int mij=(st+dr)/2;
}
void querry(int st ,int dr ,int nod){
if(start<=st&&dr<=n){
    if(Max<sol[nod]) Max=sol[nod];
}
int m=(st+dr)/2;
if(start<=m) querry(st,m,nod*2);
if(m<dr) querry(m,dr,nod*2+1);
}
void update(int st,int dr ,int nod){
if(st==dr){
    suf[nod]=val;
    pref[nod]=val;
    sol[nod]=val;
    sum[nod]=val;
    return;
}
int m=(st+dr)/2;
if(pos<=m) update(st,m,2*nod);
else  update(m+1,dr,2*nod+1);
sum[nod]=sum[2*nod]+sum[2*nod+1];
sol[nod]=max(max(sol[2*nod],sol[2*nod+1]),pref[2*nod]+suf[2*nod+1]);
pref[nod]=max(pref[2*nod],sum[2*nod]+pref[2*n+1]);
suf[nod]=max(suf[2*nod+1],sum[2*nod+1]+suf[2*nod]);
}
int main()
{

    cin>>n >>m;
    for(int i=1;i<=n;i++){
        cin>>x;
        pos=i;
        val=x;
        update(1,n,1);
    }
    for(int i=1;i<=m;i++){
        cin>>a >>b;

         Max=-1;
         start=a;
         finish=b;
         querry(1,n,1);
            cout<<Max;


    }
    return 0;
}