#include <fstream>
#include <limits.h>
#include <iostream>
#include <algorithm>
using namespace std;
ifstream f("sequencequery.in");
ofstream g ("sequencequery.out");
struct ele
{
    long long full;
     long long sdr;
    long long ssm;
    long long sst;
};
ele v[400050];
long long x,n,m,i,sola,b,adaugat,sol,a;
void build(int nod, int st, int dr)
{
    if(st==dr)
    {
        f>>x;
    v[nod].full=x;
    v[nod].sst=x;
    v[nod].sdr=x;
    v[nod].ssm=x;
    }
    else
        {
        int mid=(st+dr)/2;
        build(2*nod,st,mid);
        build(2*nod+1,mid+1,dr);
        v[nod].full=v[2*nod].full+v[2*nod+1].full;
        v[nod].sst=max(v[2*nod].sst,v[2*nod].full+v[2*nod+1].sst);
        v[nod].sdr=max(v[2*nod+1].sdr,v[2*nod].sdr+v[2*nod+1].full);
        x=max(v[2*nod].ssm,v[2*nod+1].ssm);
        v[nod].ssm=max(x,v[2*nod].sdr+v[2*nod+1].sst);
    }
}
void query(int nod,int st, int dr, int a, int b)
{
    if(a<=st && b>=dr){
        x=max(v[nod].ssm,v[nod].sst+adaugat);
        sol=max(sol,x);
        adaugat=max(adaugat+v[nod].full, v[nod].sdr);
        sol=max(sol,adaugat);
    }
    else
    {
        int mid=(st+dr)/2;
        if(a<=mid)
            query(2*nod,st,mid,a,b);
        if(b>mid)
            query(2*nod+1,mid+1,dr,a,b);
    }
}
int main()
{   f>>n>>m;
    build(1,1,n);
    for(i=1;i<=m;i++){
        f>>a>>b;
        sol=adaugat=INT_MIN;
        query(1,1,n,a,b);
        g<<sol<<"\n";
    }
    return 0;
}