<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>

class Solution:
    def maxBalancedSubsequenceSum(self, nums: List[int]) -> int:
        
        from sortedcontainers import SortedDict
        
        max_left = SortedDict() # key: nums[i] - i, value: max subseq sum  on its left
        
        for i in range(len(nums)):
            
            if nums[i] - i in max_left:
                
                # if nums[i] - i exists already, we update its max subseq sum
                # the same idea of brute force two for-loop DP -> TLE
                # for i in range(len(nums)):
                #    for j in range(i):
                #        if nums[i] - nums[j] >= i - j:
                #            dp[i] = max(dp[i], dp[j] + nums[i])
				# return max(dp)
				
                max_left[nums[i] - i] = max(max_left[nums[i] - i], max(max_left[nums[i] - i] + nums[i], nums[i]))
            
            else:
                
                # find the largest nums[j] - j that is smaller than nums[i] - i
                prev_idx = max_left.bisect_left(nums[i] - i) 
                
                # >>> a
                # SortedSet([3, 5])
                # >>> a.bisect_right(2)
                # 0 --> return 0 since 2 is the smallest
                # >>> a.bisect_right(4)
                # 1 --> return non-zero, so (returned idx - 1) is the largest value smaller than 4
                
                if prev_idx == 0:
                    max_left[nums[i] - i] = nums[i] # nums[i] - i is the smallest, max subseq sum is nums[i]
                else:
                    # SortedDict: peekitem(index) will return (key, value) pair
                    max_left[nums[i] - i] = max(max_left.peekitem(prev_idx-1)[1] + nums[i], nums[i])
                    
            # find the next nums[x] - x that is greater than nums[i] - i
            next_idx = max_left.bisect_right(nums[i] - i)
            
            # Use while loop to remove any (nums[x] - x) that is larger than (nums[i] - i), but has smallest max subseq sum
            while next_idx < len(max_left.keys()) and max_left.peekitem(next_idx)[1] <= max_left[nums[i] - i]:
                # SortedDict: popitem(index) will pop and return (key, value) pair
                max_left.popitem(next_idx)
                    
        return max(max_left.values())
33800