#include<fstream>
#define NMAX 100005
const long long INF = 2000000000000000LL;
using namespace std;
FILE *in,*out;

long long maxll(long long a,long long b)
{
    if(a>b)
        return a;
    return b;
}

typedef struct arbint
{
    int max;
    int st;
    int dr;
    int s;
};
arbint v[5*NMAX];
long long n,m,poz,i,val,start,finish;
long long rasp;


void Update(int,int,int);
void query(int,int,int);


int main()
{
    ifstream in("sequencequery.in");
    ofstream out("sequencequery.out");
    in>>n>>m;
    for(i=1;i<=n;i++)
    {
        in>>val;
        poz=i;
        Update(1,1,n);
    }
    for(i=1;i<=m;i++)
    {
        in>>start>>finish;
        rasp=-INF;
        val=0;
        query(1,1,n);
        out<<rasp<<"\n";

    }
    in.close();
    out.close();
    return 0;
}

void Update(int nod,int left,int right)
{
    if(left==right)
    {
        v[nod].max=v[nod].st=v[nod].dr=v[nod].s=val;
        return;
    }
    int div=(left+right)/2;
    if(poz<=div)
        Update(2*nod,left,div);
    else
        Update(2*nod+1,div+1,right);
    long long fiu=2*nod;
    v[nod].max=max(v[fiu].dr+v[fiu+1].st , max(v[fiu].max,v[fiu+1].max));
    v[nod].s=v[fiu].s+v[fiu+1].s;
    v[nod].st=max(v[fiu].st , v[fiu].s + v[fiu+1].st);
    v[nod].dr=max(v[fiu+1].dr , v[fiu+1].s + v[fiu].dr);
}

void query(int nod,int left, int right)
{
    if(start<=left && finish>=right)
    {
        long long ret=v[nod].max;
        ret=maxll(ret , val+v[nod].st);
        val=maxll(val+v[nod].s , v[nod].dr);
        rasp=maxll(rasp,ret);
        return;
    }
    long long div=(left+right)/2;
    long long fiu=2*nod;
    if(start<=div)
        query(fiu,start,div);
    if(finish>div)
        query(fiu+1,div+1,right);
}