#include <bits/stdc++.h>

using namespace std;

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

const int INF = 2e9;

struct node
{
    int sum, suf, pref, maxim;
};

int max5 (int a, int b, int c, int d, int e)
{
    return max(a, max(b, max(c, max(d, e))));
}

class SegTree
{
protected:
    int n;
    vector<node>a;
public:
    void init (int N)
    {
        n = 1;
        while (n < N)
            n <<= 1;
        n <<= 1;
        n++;
        a.resize(n);
    }

    node merge_nodes (node st, node dr)
    {
        node p;

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

        p.maxim = max5(st.maxim, dr.maxim, st.suf + dr.pref, st.suf, dr.pref);

        return p;
    }

    void build (int nod, int st, int dr)
    {
        if (st == dr)
        {
            int x;
            in >> x;
            a[nod] = {x, x, x, x};
        }
        else
        {
            int mid = (st + dr) / 2;

            int ls = 2*nod, rs = ls+1;

            build(ls, st, mid);
            build(rs, mid+1, dr);

            a[nod] = merge_nodes(a[ls], a[rs]);
        }
    }

    node query (int nod, int st, int dr, int l, int r)
    {
        if (l <= st && dr <= r)
            return a[nod];
        int mid = (st + dr) / 2;

        if (l <= mid && mid < r)
        {
            node ls = query(2*nod, st, mid, l, r);
            node rs = query(2*nod+1, mid+1, dr, l, r);

            return merge_nodes(ls, rs);
        }
        else if (l <= mid)
            return query(2*nod, st, mid, l, r);
        else if (mid < r)
            return query(2*nod+1, mid+1, dr, l, r);
    }
};

int main()
{
    int n, q;
    in >> n >> q;

    SegTree ST;

    ST.init(n);

    ST.build(1, 1, n);

    while (q--)
    {
        int x, y;
        in >> x >> y;

        out << ST.query(1, 1, n, x, y).maxim << '\n';
    }

    return 0;
}