#include<iostream>
#include<cstdint>
#include<cstdlib>
using namespace std;

#define NMAX 100001

struct seq{
    int64_t allsum,prefsum,sufsum,maxsum;
    bool used=true;
    friend auto operator>>(istream&in,seq&s)->istream&{
        in>>s.allsum;
        s.prefsum=s.allsum;
        s.sufsum=s.allsum;
        s.maxsum=s.allsum;
        s.used=true;
        return in;
    }
    friend auto operator+(const seq&s1,const seq&s2)->seq{
        seq r;
        r.used=true;
        r.allsum=s1.allsum+s2.allsum;
        r.prefsum=max(s1.prefsum,s1.allsum+s2.prefsum);
        r.sufsum=max(s2.sufsum,s1.sufsum+s2.allsum);
        r.maxsum=max(s1.maxsum,s2.maxsum);
        r.maxsum=max(r.maxsum,r.allsum);
        r.maxsum=max(r.maxsum,r.sufsum);
        r.maxsum=max(r.maxsum,r.prefsum);
        r.maxsum=max(r.maxsum,s1.sufsum+s2.prefsum);
        return r;
    }
    auto operator+=(const seq&s)->void{
        seq*_this=new seq;
        *_this=*this;
        _this->used=true;
        _this->allsum=this->allsum+s.allsum;
        _this->prefsum=max(this->prefsum,this->allsum+s.prefsum);
        _this->sufsum=max(s.sufsum,this->sufsum+s.allsum);
        _this->maxsum=max(this->maxsum,s.maxsum);
        _this->maxsum=max(_this->maxsum,_this->allsum);
        _this->maxsum=max(_this->maxsum,_this->sufsum);
        _this->maxsum=max(_this->maxsum,_this->prefsum);
        _this->maxsum=max(_this->maxsum,this->sufsum+s.prefsum);
        memcpy(this,_this,sizeof(seq));
    }
}*aint;
auto init(int64_t nod,int64_t st,int64_t dr)->void{
    if(st==dr){
        cin>>aint[nod];
        return;
    }
    auto mij=(st+dr)/2;
    init(2*nod,st,mij);
    init(2*nod+1,mij+1,dr);
    aint[nod]=aint[2*nod]+aint[2*nod+1];
}
auto query(int64_t nod,int64_t st,int64_t dr,const int64_t&x,const int64_t&y,seq&ans)->void{
    if(y<st||dr<x)return;
    if(x<=st&&dr<=y){
        if(!ans.used){
            ans=aint[nod];
            return;
        }
        ans+=aint[nod];
        return;
    }
    auto mij=(st+dr)/2;
    query(2*nod,st,mij,x,y,ans);
    query(2*nod+1,mij+1,dr,x,y,ans);
}
int64_t n,q;
auto print(int64_t nod,int64_t st,int64_t dr)->void{
    cout<<aint[nod].allsum<<" ";
    if(dr==n)cout<<endl;
    if(st==dr)return;
    auto mij=(st+dr)/2;
    print(2*nod,st,mij);
    print(2*nod+1,mij+1,dr);
}
auto main()->int32_t{
    freopen("sequencequery.in","r",stdin);
    freopen("sequencequery.out","w",stdout);
    cin>>n>>q;
    aint=(seq*)malloc(sizeof(seq)*4*n);
    init(1,1,n);
    // print(1,1,n);
    for(;q;--q){
        seq ans;
        ans.used=false;
        int64_t x,y;
        cin>>x>>y;
        query(1,1,n,x,y,ans);
        cout<<ans.maxsum<<"\n";
    }
    return EXIT_SUCCESS;
}