#include <bits/stdc++.h>
#define int long long

using namespace std;

struct tree
{
    int sum;
    int pref;
    int suf;
    int smax;
};

int v[100005];
tree aib[400005];

tree combine(tree st, tree dr)
{
    tree curr;

    curr.sum = st.sum + dr.sum;

    curr.pref = max(st.pref, st.sum + dr.pref);
    curr.suf = max(dr.suf, dr.sum + st.suf);
    curr.smax = max(st.suf + dr.pref, max(st.smax, dr.smax));

    return curr;
}

void build(int node, int st, int dr)
{
    if(st == dr)
    {
        aib[node].sum = v[st];
        aib[node].smax = v[st];
        aib[node].suf = v[st];
        aib[node].pref = v[st];
    }
    else
    {
        int mij = (st+dr)/2;

        build(node*2, st, mij);
        build(node*2+1, mij+1, dr);

        aib[node] = combine(aib[node*2], aib[node*2+1]);
    }
}

tree query(int node, int st, int dr, int qst, int qdr)
{
    if(qst <= st && dr <= qdr)
        return aib[node];
    else
    {
        int mij = (st+dr)/2;

        if(qdr <= mij)
            return query(node*2, st, mij, qst, qdr);
        if(mij + 1 <= qst)
            return query(node*2+1, mij+1, dr, qst, qdr);

        return combine(query(node*2, st, mij, qst, qdr), query(node*2+1, mij+1, dr, qst, qdr));
    }
}

int32_t main()
{
    ifstream cin("sequencequery.in");
    ofstream cout("sequencequery.out");
    int n, m;
    cin>>n>>m;
    for(int i=1; i<=n; i++)
        cin>>v[i];

    build(1, 1, n);

    int a, b;
    for(int i=1; i<=m; i++)
    {
        cin>>a>>b;
        cout<<query(1, 1, n, a, b).smax<<'\n';
    }


    return 0;
}