#include<fstream>

using namespace std;

ifstream cin("sequencequery.in");
ofstream cout("sequencequery.out");

const int N=100003;
struct data{long long sum,  pre,  suf,  ans;} tree[4*N];
int n,m,i,a[N],x,y;


data make_data(int x)
{
    data d;
    d.sum=d.ans=d.pre=d.suf=x;
    return d;
}

data combine(data a, data b)
{
    data d;
    d.sum=a.sum+b.sum;
    d.ans=max(max(a.ans,b.ans),a.suf+b.pre);
    d.pre=max(a.pre,a.sum+b.pre);
    d.suf=max(b.suf,b.sum+a.suf);
    return d;
}

int build(int k, int l, int r)
{
    if (l==r) tree[k]=make_data(a[l]);
    else{
        int mij=(l+r)/2;
        build(2*k,l,mij);
        build(2*k+1,mij+1,r);
        tree[k]=combine(tree[2*k],tree[2*k+1]);
    }
}

data query(int k, int L, int R, int l, int r)
{
    if (l==L && r==R) return tree[k];
    int mij=(L+R)/2;
    if (r<=mij) return query(2*k,L,mij,l,r);
    if (l>mij) return query(2*k+1,mij+1,R,l,r);
    return combine(
                   query(2*k,L,mij,l,mij),
                   query(2*k+1,mij+1,R,mij+1,r)
                   );
}

int main()
{
    cin>>n>>m;
    for (i=1;i<=n;i++)cin>>a[i];
    build(1,1,n);

    while (m--){
        cin>>x>>y
        ;
        cout<<query(1,1,n,x,y).ans<<"\n";
    }
    return 0;
}