#include<fstream>
const int NMAX=100005;
const long long INF = 2000000000000000LL;
using namespace std;


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

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=max(val,0);
        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);

    v[nod].max=max(v[2*nod].dr+v[2*nod+1].st , max(v[2*nod].max,v[2*nod+1].max));
    v[nod].s=v[2*nod].s+v[2*nod+1].s;
    v[nod].st=max(v[2*nod].st , v[2*nod].s + v[2*nod+1].st);
    v[nod].dr=max(v[2*nod+1].dr , v[2*nod+1].s + v[2*nod].dr);
}

void query(int nod,int left, int right)
{
    if(start<=left && right<=finish)
    {
        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;
    }
    int div=(left+right)>>1;
    if(start<=div)
        query(2*nod,left,div);
    if(finish>div)
        query(2*nod+1,div+1,right);
}