<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:
        mapping = {val: i for i, val in enumerate(sorted(set(num - i for i, num in enumerate(nums))))}
        st = ST([-inf] * len(mapping), default=-inf, func=max)
        for i, num in enumerate(nums):
            # nums[j] - nums[i] >= j - i
            # nums[j] >= j - i + nums[i]
            # nums[j] - j >= nums[i] - i
            limit = mapping[num - i]
            max_sum = st[:limit + 1]
            max_sum = max(max_sum + num, num)
            st[limit] = max_sum
        return st[:]
class ST:
    def __init__(self, data, default=0, func=lambda x, y: x + y, offset=0, init=False):
        self._default = default
        self._func = func
        self._len = len(data)
        self._size = _size = 1 << (self._len - 1).bit_length()
        self._offset = offset

        self.data = [default] * (2 * _size)
        self.data[_size:_size + self._len] = data
        if init:
            for i in reversed(range(_size)):
                self.data[i] = func(self.data[i + i], self.data[i + i + 1])

    def __delitem__(self, idx):
        self[idx] = self._default

    def __getitem__(self, key):
        if isinstance(key, slice):
            start = key.start if key.start is not None else -self._offset
            stop = key.stop if key.stop is not None else -self._offset + self._len
            return self.query(start, stop)
        else:
            return self.data[key + self._size + self._offset]

    def __setitem__(self, idx, value):
        idx += self._size + self._offset
        self.data[idx] = value
        idx >>= 1
        while idx:
            self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
            idx >>= 1

    def __len__(self):
        return self._len

    def query(self, start, stop):
        """func of data[start, stop)"""
        start = max(start, -self._offset) + self._offset
        stop = min(stop, -self._offset + self._len) + self._offset
        start += self._size
        stop += self._size

        res_left = res_right = self._default
        while start < stop:
            if start & 1:
                res_left = self._func(res_left, self.data[start])
                start += 1
            if stop & 1:
                stop -= 1
                res_right = self._func(self.data[stop], res_right)
            start >>= 1
            stop >>= 1

        return self._func(res_left, res_right)
    
    def query_wraparound(self, start, end):
        res = 0
        if start < -self._offset:
            diff = self._offset - start
            q, r = divmod(diff, self._len)
            res += self.data[1] * q + self[self._len - r:]
        if end > -self._offset + self._len:
            diff = end - (self._len - self._offset)
            q, r = divmod(diff, self._len)
            res += self.data[1] * q + self[:r - self._offset]
        return res + self[start:end]

    def find_k(self, k):
        """find the maximum idx where func of data[:idx] <= k"""
        return BS.findmax(
            -self._offset,
            -self._offset + self._len,
            lambda idx: self.query(-self._offset, idx) <= k
        )

    def query_all(self):
        """func of data[:]"""
        return self.data[1]

    def __repr__(self):
        return "ST({0})".format(self.data[self._size:self._size + self._len])

class BS:
    @staticmethod
    def findmin(low: int, high: int, check) -> int:
        """find the minimum int x which make check true"""
        while low < high - 1:
            mid = low + (high - low) // 2
            if check(mid):
                high = mid
            else:
                low = mid
        return low if check(low) else high

    @staticmethod
    def findmax(low: int, high: int, check) -> int:
        """find the maximum int x which make check true"""
        while low < high - 1:
            mid = low + (high - low) // 2
            if check(mid):
                low = mid
            else:
                high = mid
        return high if check(high) else low

    @staticmethod
    def find_float_left(low: float, high: float, check, error=1e-6) -> float:
        """find the minimum float x which make check true"""
        while low < high - error:
            mid = low + (high - low) / 2
            if check(mid):
                high = mid
            else:
                low = mid
        return low if check(low) else high

    @staticmethod
    def find_float_right(low: float, high: float, check, error=1e-6) -> float:
        """find the maximum float x which make check true"""
        while low < high - error:
            mid = low + (high - low) / 2
            if check(mid):
                low = mid
            else:
                high = mid
        return high if check(high) else low
44200