#include <fstream>
#define int long long
using namespace std;
ifstream fin("sequencequery.in");
ofstream fout("sequencequery.out");
int n, m, i, j, ans, x, y, v[100005];
struct arb
{
    int sum, pref, suf, maxi;
}a[400005];
void build(int nod, int st, int dr)
{
    if(st==dr)
        a[nod].sum=a[nod].pref=a[nod].suf=a[nod].maxi=v[st];
    else
    {
        int mij=(st+dr)/2;
        build(2*nod, st, mij);
        build(2*nod+1, mij+1, dr);
        a[nod].sum=a[2*nod].sum+a[2*nod+1].sum;
        a[nod].pref=max(a[nod].pref, max(a[2*nod].pref, a[2*nod].sum+a[2*nod+1].pref));
        a[nod].suf=max(a[nod].suf, max(a[2*nod+1].suf, a[2*nod].suf+a[2*nod+1].sum));
        a[nod].maxi=max(a[nod].maxi, max(a[2*nod].sum, max(a[2*nod+1].sum, a[2*nod].suf+a[2*nod+1].pref)));
    }
}
int query(int nod, int st, int dr, int l, int r)
{
    if(l<=st && dr<=r)
    {
        ans=max(ans, a[nod].maxi);
        return ans;
    }
    else
    {
        int mij=(st+dr)/2;
        if(l<=mij)
            query(2*nod, st, mij, l, r);
        if(r>mij)
            query(2*nod+1, mij+1, dr, l, r);
    }
}
signed main()
{
    fin>>n>>m;
    for(i=1; i<=n; i++)
        fin>>v[i];
    build(1, 1, n);
    while(m--)
    {
        fin>>x>>y;
        ans=-1e9;
        query(1, 1, n, x, y);
        fout<<ans<<'\n';
    }
    return 0;
}