<p>You are given a <strong>0-indexed</strong> integer array <code>nums</code>.</p>

<p>A <strong>subsequence</strong> of <code>nums</code> having length <code>k</code> and consisting of <strong>indices</strong> <code>i<sub>0</sub>&nbsp;&lt;&nbsp;i<sub>1</sub> &lt;&nbsp;... &lt; i<sub>k-1</sub></code> is <strong>balanced</strong> if the following holds:</p>

<ul>
	<li><code>nums[i<sub>j</sub>] - nums[i<sub>j-1</sub>] &gt;= i<sub>j</sub> - i<sub>j-1</sub></code>, for every <code>j</code> in the range <code>[1, k - 1]</code>.</li>
</ul>

<p>A <strong>subsequence</strong> of <code>nums</code> having length <code>1</code> is considered balanced.</p>

<p>Return <em>an integer denoting the <strong>maximum</strong> possible <strong>sum of elements</strong> in a <strong>balanced</strong> subsequence of </em><code>nums</code>.</p>

<p>A <strong>subsequence</strong> of an array is a new <strong>non-empty</strong> array that is formed from the original array by deleting some (<strong>possibly none</strong>) of the elements without disturbing the relative positions of the remaining elements.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [3,3,5,6]
<strong>Output:</strong> 14
<strong>Explanation:</strong> In this example, the subsequence [3,5,6] consisting of indices 0, 2, and 3 can be selected.
nums[2] - nums[0] &gt;= 2 - 0.
nums[3] - nums[2] &gt;= 3 - 2.
Hence, it is a balanced subsequence, and its sum is the maximum among the balanced subsequences of nums.
The subsequence consisting of indices 1, 2, and 3 is also valid.
It can be shown that it is not possible to get a balanced subsequence with a sum greater than 14.</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [5,-1,-3,8]
<strong>Output:</strong> 13
<strong>Explanation:</strong> In this example, the subsequence [5,8] consisting of indices 0 and 3 can be selected.
nums[3] - nums[0] &gt;= 3 - 0.
Hence, it is a balanced subsequence, and its sum is the maximum among the balanced subsequences of nums.
It can be shown that it is not possible to get a balanced subsequence with a sum greater than 13.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> nums = [-2,-1]
<strong>Output:</strong> -1
<strong>Explanation:</strong> In this example, the subsequence [-1] can be selected.
It is a balanced subsequence, and its sum is the maximum among the balanced subsequences of nums.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>
	<li><code>-10<sup>9</sup> &lt;= nums[i] &lt;= 10<sup>9</sup></code></li>
</ul>

import bisect

class MonotoneMap:
    def __init__(self):
        self._list = []
        self._values = []

    def insert(self, y, value):
        index_y = bisect.bisect_left(self._list, y)
        index_v = bisect.bisect_left(self._values, value)

        if len(self._list) == 0:
            self._list.append(y)
            self._values.append(value)
            return

        if index_y == len(self._list):
            if self._values[-1] >= value: return
            self._values.append(value)
            self._list.append(y)
            return

        if index_y == 0:
            for _ in range(index_y, index_v):
                del self._list[index_y]
                del self._values[index_y] 
            if len(self._list) == 0 or self._list[0] != y:
                self._values.insert(0, value)
                self._list.insert(0, y)    
            return       

        if self._values[index_y-1] >= value : return
        for _ in range(index_y, index_v):
            del self._list[index_y]
            del self._values[index_y]
        if len(self._list) == index_y or self._list[index_y] != y:
            self._list.insert(index_y, y)
            self._values.insert(index_y, value)

    def search(self, query):
        index = bisect.bisect_left(self._list, query)
        if len(self._list) == 0: return None
        if index == 0 and self._list[0] > query: return None
        if index < len(self._list) and self._list[index] == query:
            return self._values[index]
        return self._values[index-1]

    def __repr__(self):
        return repr(self._list) + repr(self._values)

class Solution:
    def maxBalancedSubsequenceSum(self, nums: List[int]) -> int:
        n = len(nums)
        cand = MonotoneMap()
        res = -10**9

        for i in range(n):
            res = max(res, nums[i])
            b_entry = cand.search(nums[i] - i)

            if b_entry != None and b_entry > 0:
                b_value = b_entry + nums[i]
                if b_value > nums[i]:
                    res = max(res, b_value)
                    cand.insert(nums[i] - i, b_entry + nums[i])
            else:
                cand.insert(nums[i] - i, nums[i])

        return res
32299