#include <bits/stdc++.h>
using namespace std;

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

#define ll long long

const ll vec_len = 100001;
struct sumNode
{
    ll sumLeft = 0;
    ll sumRight = 0;
    ll sum = 0;
    ll sumMax = 0;
};
ll vec[vec_len];
sumNode tree[vec_len * 4];

void tree_build(ll node, ll left, ll right)
{
    if (left == right)
    {
        tree[node].sumLeft = tree[node].sumRight = tree[node].sum = tree[node].sumMax = vec[left];
        return;
    }

    ll mid = (left + right) / 2;
    tree_build(node * 2, left, mid);
    tree_build(node * 2 + 1, mid + 1, right);

    tree[node].sum = tree[node * 2].sum + tree[node * 2 + 1].sum;
    tree[node].sumLeft = max(tree[node * 2].sum + tree[node * 2 + 1].sumLeft, tree[node * 2].sumLeft);
    tree[node].sumRight = max(tree[node * 2 + 1].sum + tree[node * 2].sumRight, tree[node * 2 + 1].sumRight);
    tree[node].sumMax = max(tree[node * 2].sumRight + tree[node * 2 + 1].sumLeft, max(tree[node].sumRight, tree[node].sumLeft));
    tree[node].sumMax = max(tree[node].sumMax, max(tree[node * 2].sumMax, tree[node * 2 + 1].sumMax));
}

void tree_update(ll node, ll left, ll right, ll pos)
{
    if (left == right)
    {
        tree[node].sumLeft = tree[node].sumRight = tree[node].sum = tree[node].sumMax = vec[left];
        return;
    }

    ll mid = (left + right) / 2;
    if (pos <= mid)
        tree_update(node * 2, left, mid, pos);
    else
        tree_update(node * 2 + 1, mid + 1, right, pos);

    tree[node].sum = tree[node * 2].sum + tree[node * 2 + 1].sum;
    tree[node].sumLeft = max(tree[node * 2].sum + tree[node * 2 + 1].sumLeft, tree[node * 2].sumLeft);
    tree[node].sumRight = max(tree[node * 2 + 1].sum + tree[node * 2].sumRight, tree[node * 2 + 1].sumRight);
    tree[node].sumMax = max(tree[node * 2].sumRight + tree[node * 2 + 1].sumLeft, max(tree[node].sumRight, tree[node].sumLeft));
    tree[node].sumMax = max(tree[node].sumMax, max(tree[node * 2].sumMax, tree[node * 2 + 1].sumMax));
}

sumNode tree_query(ll node, ll left, ll right, ll qleft, ll qright)
{
    sumNode ans;
    ans.sumLeft = ans.sumRight = ans.sum = ans.sumMax = LONG_LONG_MIN;

    if (qright < left || right < qleft)
        return ans;

    else if (qleft <= left && right <= qright)
        return tree[node];

    ll mid = (left + right) / 2;

    if (qright <= mid)
        return tree_query(node * 2, left, mid, qleft, qright);

    else if (mid < qleft)
        return tree_query(node * 2 + 1, mid + 1, right, qleft, qright);

    sumNode qleftAns = tree_query(node * 2, left, mid, qleft, qright);
    sumNode qrightAns = tree_query(node * 2 + 1, mid + 1, right, qleft, qright);

    ans.sum = qleftAns.sum + qrightAns.sum;
    ans.sumLeft = max(qleftAns.sum + qrightAns.sumLeft, qleftAns.sumLeft);
    ans.sumRight = max(qrightAns.sum + qleftAns.sumRight, qrightAns.sumRight);
    ans.sumMax = max(qleftAns.sumRight + qrightAns.sumLeft, max(ans.sumRight, ans.sumLeft));
    ans.sumMax = max(ans.sumMax, max(qleftAns.sumMax, qrightAns.sumMax));

    return ans;
}

int main()
{
    ll n, m;
    fin >> n >> m;

    for (ll i = 1; i <= n; i++)
        fin >> vec[i];

    tree_build(1, 1, n);

    for (ll q = 1; q <= m; q++)
    {
        ll t, x, y;
        fin >> x >> y;

        fout << tree_query(1, 1, n, x, y).sumMax << "\n";
    }

    return 0;
}