#include <bits/stdc++.h>

using namespace std;

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

#define int long long

struct aint_node
{
    int ssm,prefmax,sufmax,sum;
};

aint_node join(aint_node l,aint_node r)
{
    aint_node rez;
    rez.ssm = max(l.sufmax + r.prefmax,max(l.ssm,r.ssm));
    rez.prefmax = max(l.prefmax,l.sum + r.prefmax);
    rez.sufmax = max(r.sufmax,r.sum + l.sufmax);
    rez.sum = l.sum + r.sum;
    return rez;
}

int n,q,a[100005];
aint_node aint[400005];

void build(int nod,int l,int r)
{
    if (l == r)
        aint[nod].ssm = aint[nod].prefmax = aint[nod].sufmax = aint[nod].sum = a[l];
    else
    {
        int mij = (l + r) / 2;
        build(2 * nod,l,mij);
        build(2 * nod + 1,mij + 1,r);
        aint[nod] = join(aint[2 * nod],aint[2 * nod + 1]);
    }
}

aint_node query(int nod,int l,int r,int st,int dr)
{
    if (st <= l and r <= dr)
        return aint[nod];
    int mij = (l + r) / 2;
    if (dr <= mij)
        return query(2 * nod,l,mij,st,dr);
    else if (st > mij)
        return query(2 * nod + 1,mij + 1,r,st,dr);
    else
        return join(query(2 * nod,l,mij,st,dr),query(2 * nod + 1,mij + 1,r,st,dr));
}

signed main()
{
    in >> n >> q;
    for (int i = 1; i <= n; i++)
        in >> a[i];
    build(1,1,n);
    for (int i = 1; i <= q; i++)
    {
        int l,r;
        in >> l >> r;
        out << query(1,1,n,l,r).ssm << '\n';
    }
    return 0;
}