<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 SegmentTree:
    def __init__(self, n: int):
        self.len = n
        self.tree = [0 for _ in range(4*n)]
        self.lazy = [0 for _ in range(4*n)]
    
    def update(self, pos: int, val: int) -> None:
        self._update(0, self.len-1, 0, pos, pos, val)
    
    def query(self, qleft: int, qright: int) -> int:
        return self._query(0, self.len-1, 0, qleft, qright)

    def _update(self, left: int, right: int, index: int, uleft: int, uright: int, uval: int) -> None:
        if self.lazy[index] != 0:
            self.tree[index] += self.lazy[index]
            if left != right:
                self.lazy[2*index+1] += self.lazy[index]
                self.lazy[2*index+2] += self.lazy[index]
            self.lazy[index] = 0

        if uright < left or right < uleft:
            return
        if uleft <= left and right <= uright:
            self.tree[index] += uval
            if left != right:
                self.tree[2*index+1] += uval
                self.tree[2*index+2] += uval
            return
        mid = (left + right) // 2
        self._update(left, mid, 2*index+1, uleft, uright, uval)
        self._update(mid+1, right, 2*index+2, uleft, uright, uval)
        self.tree[index] = max(self.tree[2*index+1], self.tree[2*index+2])

    def _query(self, left: int, right: int, index: int, qleft: int, qright: int) -> int:
        if self.lazy[index] != 0:
            self.tree[index] += self.lazy[index]
            if left != right:
                self.lazy[2*index+1] += self.lazy[index]
                self.lazy[2*index+2] += self.lazy[index]
            self.lazy[index] = 0

        if qright < left or right < qleft:
            return -inf
        if qleft <= left and right <= qright:
            return self.tree[index]
        mid = (left + right) // 2
        return max(
            self._query(left, mid, 2*index+1, qleft, qright),
            self._query(mid+1, right, 2*index+2, qleft, qright),
        )

class Solution:
    def maxBalancedSubsequenceSum(self, nums: List[int]) -> int:
        n = len(nums)
        segtree = SegmentTree(n)
        nidx = [[nums[i] - i, i] for i in range(n)]
        nidx.sort()
        mapping = {i: j for j, (num, i) in enumerate(nidx)}

        answer = -inf
        for i in range(n - 1, -1, -1):
            j = mapping[i]
            f_i = nums[i] + segtree.query(j, n - 1)
            answer = max(answer, f_i)
            segtree.update(j, f_i)
        return answer
63000