#include <bits/stdc++.h>

using namespace std;

ifstream in("arbint.in");
ofstream out("arbint.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]);
}

const int INF = 1e9;

ST query(int a, int b, int k = 1, int st = 1, int dr = n)
{
     if(st > dr || dr < a || b < st)
        return {-INF, -INF, -INF, -INF};
    if(a <= st && dr <= b)
        return tree[k];
    return combine(query(a, b, 2 * k, st, (st + dr) / 2), query(a, b, 2 * k + 1, (st + dr) / 2 + 1, dr));
}

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(st, dr).scmax << '\n';
    }
    return 0;
}