<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 SegTree:
    # agg - max, min, sum etc: any function (x,y) => z
    def __init__(self, n, EMPTY_VALUE, agg) -> None:
        super().__init__()
        self.n = n
        self.val = [EMPTY_VALUE] * (2 * n)
        self.EMPTY_VALUE = EMPTY_VALUE
        self.agg = agg

    def initialize(self, arr):
        for i in reversed(range(self.n)):
            self.val[self.n + i] = arr[i]
        for i in reversed(range(self.n)):
            self.val[i] = self.agg(self.val[i << 1], self.val[i << 1 | 1])

    def clear(self):
        for i in range(2 * self.n):
            self.val[i] = self.EMPTY_VALUE

    def set(self, idx, val):
        idx += self.n
        self.val[idx] = val
        while idx > 1:
            self.val[idx >> 1] = self.agg(self.val[idx], self.val[idx ^ 1])
            idx >>= 1

    def get(self, idx):
        return self.val[idx + self.n]

    # l,r - inclusive
    def query(self, l, r):
        r += 1
        l += self.n
        r += self.n
        res = self.EMPTY_VALUE
        while l < r:
            if l & 1 != 0:
                res = self.agg(res, self.val[l])
                l += 1
            if r & 1 != 0:
                res = self.agg(res, self.val[r - 1])
                r -= 1
            l >>= 1
            r >>= 1
        return res

    def __getitem__(self, key):
        if isinstance(key, slice): return self.query(key.start,key.stop-1)
        return self.get(key)

    def __setitem__(self, key, value):
        self.set(key, value)


class Solution:
    def maxBalancedSubsequenceSum(self, nums: List[int]) -> int:
        n=len(nums)
        st=SegTree(n,float('-inf'),max)
        for i in sorted(range(n),key=lambda i:nums[i]-i):
            st[i]=nums[i]+max(0,st[0:i])
        return st[0:n]
35300