#include <iostream>
#include <fstream>

using namespace std;

ifstream x("sequencequery.in");
ofstream y("sequencequery.out");

int n,m,i,j,nr,poz,val,start,finish,sol,pos,w[100002],sum,a,b;

struct elem
{
    int pi,ps,lg,a;
}v[400022];

void update(int nod, int left, int right)
{
    if(left==right)
    {
        v[nod].pi=v[nod].ps=v[nod].a=v[nod].lg=w[right];
        return;
    }

    int mij=(left+right)/2;

    update(nod*2,left,mij);
    update(nod*2+1,mij+1,right);

    v[nod].pi=max(v[nod*2].pi,v[nod*2].lg+v[nod*2+1].pi);
    v[nod].ps=max(v[nod*2+1].ps,v[nod*2+1].lg+v[nod*2].ps);
    v[nod].lg=v[nod*2].lg+v[nod*2+1].lg;
    v[nod].a=max(v[nod*2].a,max(v[nod*2+1].a,v[nod*2+1].pi+v[nod*2].ps));

}

void query(int nod, int left, int right)
{
    if(left>=start && right<=finish)
    {
        if(sum<0)
            sum=0;
        sol=max(sol,max(sum+v[nod].pi,v[nod].a));
        sum=max(sum+v[nod].lg,v[nod].ps);
        return;
    }

    int mij=(left+right)/2;

    if(start<=mij)
        query(nod*2,left,mij);
    if(finish>mij)
        query(nod*2+1,mij+1,right);
}

int main()
{
    x>>n>>m;
    for(i=1;i<=n;i++)
        x>>w[i];
    update(1,1,n);
    for(i=1;i<=m;i++)
    {
        x>>a>>b;
        sum=sol=-110000 ;
        start=a;
        finish=b;
        query(1,1,n);
        y<<sol<<'\n';
    }
    x.close();
    y.close();
    return 0;
}