#include<iostream>
#include<bitset>
using namespace std;

#define NMAX 100001
#define lb b[0]

struct _{
    int pf=0,sf=0,mx=0,al=0;
    auto operator=(const int&x)->void{
        this->pf=x;
        this->sf=x;
        this->mx=x;
        this->al=x;
        return;
    }
    friend auto operator+(const _&_1,const _&_2)->_{
        _ _3;
        _3=0;
        _3.al=_1.al+_2.al;
        _3.pf=max(_1.pf,_1.al+_2.pf);
        _3.sf=max(_2.sf,_1.sf+_2.al);
        _3.mx=max(_1.mx,_2.mx);
        _3.mx=max(_3.mx,_3.al);
        _3.mx=max(_3.mx,_3.sf);
        _3.mx=max(_3.mx,_3.pf);
        _3.mx=max(_3.mx,_1.sf+_2.pf);

        _3.al=_1.al+_2.al;
        _3.pf=max(_1.pf,_1.al+_2.pf);
        _3.sf=max(_2.sf,_1.sf+_2.al);
        _3.mx=max(_1.mx,_2.mx);
        _3.mx=max(_3.mx,_3.al);
        _3.mx=max(_3.mx,_3.sf);
        _3.mx=max(_3.mx,_3.pf);
        _3.mx=max(_3.mx,_1.sf+_2.pf);
        return _3;
    }
    auto operator+=(const _&__)->void{
        *this=*this+__;
    }
    friend auto operator<<(ostream&out,const _&__)->ostream&{
        out<<max(__.al,max(__.pf,max(__.sf,__.mx)));
        return out;
    }
    friend auto operator>>(istream&in,_&__)->istream&{
        int x;
        in>>x;
        __=x;
        return in;
    }
}aint[4*NMAX],ans;
int n,q;
bitset<1>b;
auto init(int nod,int st,int dr)->void{
    if(st==dr){
        cin>>aint[nod];
        return;
    }
    int 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(int nod,int st,int dr,const int&x,const int&y)->void{
    if(y<st||dr<x)return;
    if(x<=st&&dr<=y){
        if(!lb){
            lb=true;
            ans=aint[nod];
            return;
        }
        ans+=aint[nod];
        return;
    }
    int mij=(st+dr)/2;
    query(2*nod,st,mij,x,y);
    query(2*nod+1,mij+1,dr,x,y);
}
auto print(int nod,int st,int dr)->void{
    cout<<aint[nod].al<<" ";
    if(dr==n)cout<<endl;
    if(st==dr)return;
    int mij=(st+dr)/2;
    print(2*nod,st,mij);
    print(2*nod+1,mij+1,dr);
}
auto main(void)->signed{
    #ifndef LOCAL
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
        cout.tie(nullptr);
    #endif // LOCAL
    freopen("sequencequery.in","r",stdin);
    freopen("sequencequery.out","w",stdout);
    cin>>n>>q;
    init(1,1,n);
    // print(1,1,n);
    for(;q;--q){
        int x,y;
        cin>>x>>y;
        if(x>y)swap(x,y);
        ans=0;
        lb=false;
        query(1,1,n,x,y);
        cout<<ans<<"\n";
    }
    return 0;
}