#include<fstream>
#include<cmath>
using namespace std;
int n,m,v[100100];
int poz,val,A,B;
long long S,rez;
struct Nod{long long L,R,best,sum;};
Nod AInt[525000];
 
inline void Build(int nod,int st,int dr)
{
    if(st==dr)
    {
        AInt[nod].L=AInt[nod].R=AInt[nod].best=AInt[nod].sum=v[st];
        return;
    }
    int mij=(st+dr)/2,fiu=2*nod;
    Build(fiu,st,mij);
    Build(fiu+1,mij+1,dr);
    AInt[nod].L=max(AInt[fiu].L,AInt[fiu].sum+AInt[fiu+1].L);
    AInt[nod].R=max(AInt[fiu+1].R,AInt[fiu+1].sum+AInt[fiu].R);
    AInt[nod].best=max(max(AInt[fiu].best,AInt[fiu+1].best),AInt[fiu].R+AInt[fiu+1].L);
    AInt[nod].sum=AInt[fiu].sum+AInt[fiu+1].sum;
}
 
inline void Query(int nod,int st,int dr)
{
    if(A<=st && dr<=B)
    {
        if(S<0)
            S=0;
        rez=max(rez,max(AInt[nod].best,AInt[nod].L+S));
        S=max(AInt[nod].sum+S,AInt[nod].R);
        return;
    }
    int mij=(st+dr)/2,fiu=2*nod;
    if(A<=mij)
        Query(fiu,st,mij);
    if(mij+1<=B)
        Query(fiu+1,mij+1,dr);
}
 
int main()
{
    int i;
    ifstream fin("sequencequery.in");
    ofstream fout("sequencequery.out");
    fin>>n>>m;
    for(i=1;i<=n;i++)
        fin>>v[i];
    Build(1,1,n);
    for(i=1;i<=m;i++)
    {
        fin>>A>>B;
        S=0LL;
        rez=-10000000001LL;
        Query(1,1,n);
        fout<<rez<<"\n";
    }
    fin.close();
    fout.close();
    return 0;
}