#include <bits/stdc++.h>

using namespace std;
#define int long long
ifstream fin("sequencequery.in");
ofstream fout("sequencequery.out");
const int Nmax=1e5+5;
int a[Nmax],s[Nmax];
int aint[4*Nmax],pref[4*Nmax],suf[4*Nmax];
struct node
{
    int val,p,s;
};
void build(int nod,int l,int r)
{
    if(l==r)
    {
        aint[nod]=a[l];
        pref[nod]=a[l];
        suf[nod]=a[l];
        return;
    }
    int mid=(l+r)/2;
    build(2*nod,l,mid);
    build(2*nod+1,mid+1,r);
    pref[nod]=max(pref[2*nod],s[mid]-s[l-1]+pref[2*nod+1]);
    suf[nod]=max(suf[2*nod+1],s[r]-s[mid]+suf[2*nod]);
    aint[nod]=max(aint[2*nod],aint[2*nod+1]);
    aint[nod]=max(aint[nod],pref[nod]);
    aint[nod]=max(aint[nod],suf[nod]);
    aint[nod]=max(aint[nod],suf[2*nod]+pref[2*nod+1]);
    return;
}
node query(int nod,int l,int r,int st,int dr)
{
    if(st<=l && r<=dr)
    {
        ///cout<<l<<' '<<r<<' '<<aint[nod]<<' '<<pref[nod]<<' '<<suf[nod]<<'\n';
        return {aint[nod],pref[nod],suf[nod]};
    }
    int mid=(l+r)/2;
    if(dr<=mid) return query(2*nod,l,mid,st,dr);
    if(mid<st) return query(2*nod+1,mid+1,r,st,dr);
    node left=query(2*nod,l,mid,st,mid);
    node right=query(2*nod+1,mid+1,r,mid+1,dr);
    node sol;
    sol.p=max(left.p,s[mid]-s[st-1]+right.p);
    sol.s=max(right.s,s[dr]-s[mid]+left.s);
    sol.val=max(left.val,right.val);
    sol.val=max(sol.val,sol.p);
    sol.val=max(sol.val,sol.s);
    sol.val=max(sol.val,left.s+right.p);
    return sol;
}
signed main()
{
    int n,m;
    fin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        fin>>a[i];
        s[i]=s[i-1]+a[i];
    }
    build(1,1,n);
    for(int i=1;i<=m;i++)
    {
        int l,r;
        fin>>l>>r;
        fout<<query(1,1,n,l,r).val<<'\n';
    }
    return 0;
}