#include <bits/stdc++.h>
using namespace std;
ifstream fin ("sequencequery.in");
ofstream fout ("sequencequery.out");

const int MAXN=100010;


struct nod{
    long long r,p,s,sum;
}aint[4*MAXN];
int n,q;

void Update (int val, int pos, int l, int r, int node){
    if (l==r){
        aint[node].p=aint[node].s=aint[node].r=aint[node].sum=val;
        return;
    }
    int mij=(l+r)/2;
    if (mij<pos)
        Update (val,pos,mij+1,r,2*node+1);
    else
        Update (val,pos,l,mij,2*node);
    aint[node].sum=aint[2*node].sum+aint[2*node+1].sum;
    aint[node].p=max (aint[2*node].p, aint[2*node].sum+aint[2*node+1].p);
    aint[node].s=max (aint[2*node+1].s, aint[2*node+1].sum+aint[2*node].s);
    aint[node].r=max ({aint[2*node].r,aint[2*node+1].r,aint[2*node].s+aint[2*node+1].p});
}

nod Query (int node, int ql, int qr, int l, int r){
    if (l>qr || r<ql || l>r){


        nod stop;
        stop.p=stop.s=stop.r=-1e9;
        return stop;
    }

    if (ql<=l && r<=qr)
        return aint[node];

    int mij=(l+r)/2;
    nod rez1=Query (2*node,ql,qr,l,mij);
    nod rez2=Query (2*node+1,ql,qr,mij+1,r);
    nod x;
    x.r=max ({rez1.r,rez2.r,rez1.s+rez2.p});
    x.p=max ({rez1.p,rez1.s+rez2.p});
    x.s=max ({rez2.s,rez2.s+rez1.s});
    x.sum=rez1.sum+rez2.sum;
    return x;
}

int main()
{
    fin >>n>>q;
    for (int i=0;i<MAXN;++i){
        aint[i].s=aint[i].p=aint[i].r=-1e9;
    }
    for (int i=1;i<=n;++i){
        int x;
        fin >>x;
        Update (x,i,1,n,1);
        //fout <<aint[1].r<<' ';
    }


    for (int i=1;i<=q;++i){
        int a,b;
        fin >>a>>b;
        nod rez=Query (1,a,b,1,n);
        fout <<rez.r<<'\n';
    }
    fin.close ();
    fout.close ();
    return 0;
}