#include <fstream>

using namespace std;
ifstream cin("sequencequery.in");
ofstream cout("sequencequery.out");
const int N = 100009,Inf = 0x3f3f3f3f3f;
int n,m,a,b;
struct fix
{
    int val,len;
};
struct node
{
    fix pre,suf;
    int mx;
}tree[4*N];
node Merge(node a,node b,int len_a,int len_b)
{
    node c = {0,0,0,0,0};
    c.pre = a.pre;
    c.suf = b.suf;
    if(a.pre.len == len_a && c.pre.val <= a.pre.val + b.pre.val)
    {
        c.pre.val = a.pre.val + b.pre.val;
        c.pre.len = a.pre.len + b.pre.len;
    }
    if(b.suf.len == len_b && c.suf.val <= b.suf.val + a.suf.val)
    {
        c.suf.val = a.suf.val + b.suf.val;
        c.suf.len = a.suf.len + b.suf.len;
    }
    c.mx = max(a.mx,max(b.mx,max(c.pre.val,max(c.suf.val,a.suf.val + b.pre.val))));
    return c;
}
void build(int nod,int st,int dr)
{
    if(st==dr)
    {
        int x;
        cin>>x;
        tree[nod].pre.val = tree[nod].suf.val = tree[nod].mx = x;
        tree[nod].suf.len = tree[nod].pre.len = 1;
        return;
    }
    int mij = (st+dr)>>1;
    build(nod<<1,st,mij);
    build(nod<<1|1,mij+1,dr);

    tree[nod] = Merge(tree[nod<<1],tree[nod<<1|1],mij-st+1,dr-mij);
}
node query(int nod,int st,int dr,int a,int b)
{
    if(a<=st&&dr<=b)
        return tree[nod];
    int mij = (st+dr)>>1;
    int x1 = -Inf,x2 = x1;
    if(a<=mij && b>mij)
        return Merge(query(nod<<1,st,mij,a,b),query(nod<<1|1,mij+1,dr,a,b),mij-st+1,dr-mij);
    else if(a>mij)
        return query(nod<<1|1,mij+1,dr,a,b);
    else
        return query(nod<<1,st,mij,a,b);
}
int main()
{
    cin>>n>>m;
    build(1,1,n);
    while(m--)
    {
        cin>>a>>b;
        cout<<query(1,1,n,a,b).mx<<'\n';
    }
    return 0;
}