#include <bits/stdc++.h>

using namespace std;

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

const int N = 1e5 + 5;

int v[N], n, q;

struct ST
{
    int sum;
    int pref;
    int suff;
    int scmax;
};

ST tree[4 * N];

ST combine(ST st, ST dr)
{
    ST val;
    val.sum = st.sum + dr.sum;
    val.pref = max(st.pref, st.sum + dr.pref);
    val.suff = max(dr.suff, dr.sum + st.suff);
    val.scmax = max(st.suff + dr.pref, max(st.scmax, dr.scmax));
    return val;
}

void build(int nod, int st, int dr)
{
    if(st == dr)
    {
        tree[nod] = {v[st], v[st], v[st], v[st]};
        return;
    }
    int med = (st + dr) / 2;
    build(2 * nod, st, med);
    build(2 * nod + 1, med + 1, dr);
    tree[nod] = combine(tree[2 * nod], tree[2 * nod + 1]);
}

ST query(int nod, int st, int dr, int a, int b)
{
    if(a <= st && dr <= b)
    {
        return tree[nod];
    }
    int med = (st + dr) / 2;
    ST lft, rght;
    if(b <= med)
        return query(2 * nod, st, med, a, b);
    if( a >= med + 1)
        return query(2 * nod + 1, med + 1, dr, a, b);
    lft = query(2 * nod, st, med, a, b);
    rght = query(2 * nod + 1, med + 1, dr, a, b);
    return combine(lft, rght);
}

int main()
{
    in >> n >> q;
    for(int i = 1; i <= n; i++)
        in >> v[i];
    build(1, 1, n);
    while(q--)
    {
        int st, dr;
        in >> st >> dr;
        out << query(1, 1, n, st, dr).scmax << '\n';
    }
    return 0;
}