#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

ifstream fin("sequencequery.in");
ofstream fout("sequencequery.out");
#define ll long long
vector<ll> v;
struct Aint
{
    ll ssm,prefix,sufix,suma;
};
vector<Aint> aint;
Aint Update_Frunza(ll x)
{
    Aint aux;
    aux.ssm=aux.prefix=aux.sufix=aux.suma=x;
    return aux;
}
Aint Combine_Nod(Aint a,Aint b)
{
    Aint aux;
    ///ssm
        ///Avem 3 cazuri, yey
        aux.ssm=max(a.ssm,b.ssm); ///maximul este integral in una din jumatati
        aux.ssm=max(aux.ssm,a.sufix+b.prefix); ///maximul este splituit in ambele jumatati
    ///prefix
        aux.prefix=max(a.prefix,a.suma+b.prefix);
    ///sufix
        aux.sufix=max(b.sufix,a.sufix+b.suma);
    ///suma
        aux.suma=a.suma+b.suma;
    return aux;
}
void build(int nod,int st,int dr)
{
    if(st==dr)
    {
        aint[nod]=Update_Frunza(v[st]);
        return ;
    }
    int mid=(st+dr)/2;
    build(2*nod,st,mid);
    build(2*nod+1,mid+1,dr);
    aint[nod]=Combine_Nod(aint[2*nod],aint[2*nod+1]);
}

Aint query(int nod,int st,int dr,int q_st,int q_dr)
{
    //cout<<st<<" "<<dr<<" "<<q_st<<" "<<q_dr<<" "<<aint[nod].ssm<<'\n';
    if(q_st<=st && dr<=q_dr)
    {
        return aint[nod];
    }
    bool sem=0;
    int mid=(st+dr)/2;
    Aint aux;
    if(q_st<=mid)
    {
        aux=query(2*nod,st,mid,q_st,q_dr);
        sem=1;
    }
    if(mid<q_dr)
    {
        if(sem==1)
            aux=Combine_Nod(aux,query(2*nod+1,mid+1,dr,q_st,q_dr));
        else
            aux=query(2*nod+1,mid+1,dr,q_st,q_dr);
    }
    return aux;
}

int main()
{
    Aint aux;
    int n,m,i,a,b;
    fin>>n>>m;
    aint.resize(4*n);
    v.resize(n+1);
    for(i=1;i<=n;i++)
    {
        fin>>v[i];
    }
    build(1,1,n);
    for(i=1;i<=m;i++)
    {
        fin>>a>>b;
        aux=query(1,1,n,a,b);
        fout<<aux.ssm<<'\n';
    }
    return 0;
}