#include <bits/stdc++.h>

using namespace std;

const long long inf= 1e11;
int n, m;
vector <int> a;

struct node
{
    long long left, right, sum, v;
};

class SegmentTree
{
    vector <node> t;

    node mergeNodes(const node &x, const node &y)
    {
        node ans;
        ans.v = max(max(x.right + y.left, x.v), y.v);
        ans.sum = x.sum + y.sum;
        ans.right = y.right;
        if(y.right == y.sum)
             ans.right += max(x.right, 0ll);
        ans.left = x.left;
        if(x.left == x.sum)
             ans.left += max(y.left, 0ll);
        return ans;
    }

public :
    SegmentTree(int x)
    {
        t.resize(4 * x + 1);
    }

    void build(vector <int> &a, int v, int l, int r)
    {
        if(l == r)
        {
            t[v].left = a[l];
            t[v].right = a[l];
            t[v].sum = a[l];
            t[v].v = a[l];
            return;
        }
        int m = (l + r) / 2;
        build(a, 2 * v, l, m);
        build(a, 2 * v + 1, m + 1, r);
        t[v] = mergeNodes(t[2 * v], t[2 * v + 1]);
    }

    node query(int v, int l, int r, int tl, int tr)
    {
        if(tl > tr)
            return {-inf, -inf, 0, -inf};
        if(l == tl  &&  r == tr)
            return t[v];
        int m = (l + r) / 2;
        return mergeNodes(query(2 * v, l, m, tl, min(m, tr)),
                          query(2 * v + 1, m + 1, r, max(m + 1, tl), tr));
    }

    void print(int v, int l, int r)
    {
        if(l == r)
        {
            cout << l << " " << r << " " << t[v].left << " " << t[v].right << " " << t[v].sum << " " << t[v].v << "\n";
            return;
        }
        int m = (l + r) / 2;
        print(2 * v, l, m);
        print(2 * v + 1, m + 1, r);
        cout << l << " " << r << " " << t[v].left << " " << t[v].right << " " << t[v].sum << " " << t[v].v << "\n";
    }

};

int main()
{
    ios_base :: sync_with_stdio(0);
    cin.tie(0);

    freopen("sequencequery.in", "r", stdin);
    freopen("sequencequery.out", "w", stdout);

    cin >> n >> m;
    a.resize(n + 1);
    SegmentTree aint(n);

    for(int i = 1; i <= n; i ++)
        cin >> a[i];

    aint.build(a, 1, 1, n);
//    aint.print(1, 1, n);
    for(int i = 1; i <= m; i ++)
    {
        int x, y;
        cin >> x >> y;
        cout << aint.query(1, 1, n, x, y).v << "\n";
    }
    return 0;
}