<p>You are given an integer array <code>rewardValues</code> of length <code>n</code>, representing the values of rewards.</p>

<p>Initially, your total reward <code>x</code> is 0, and all indices are <strong>unmarked</strong>. You are allowed to perform the following operation <strong>any</strong> number of times:</p>

<ul>
	<li>Choose an <strong>unmarked</strong> index <code>i</code> from the range <code>[0, n - 1]</code>.</li>
	<li>If <code>rewardValues[i]</code> is <strong>greater</strong> than your current total reward <code>x</code>, then add <code>rewardValues[i]</code> to <code>x</code> (i.e., <code>x = x + rewardValues[i]</code>), and <strong>mark</strong> the index <code>i</code>.</li>
</ul>

<p>Return an integer denoting the <strong>maximum </strong><em>total reward</em> you can collect by performing the operations optimally.</p>

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

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">rewardValues = [1,1,3,3]</span></p>

<p><strong>Output:</strong> <span class="example-io">4</span></p>

<p><strong>Explanation:</strong></p>

<p>During the operations, we can choose to mark the indices 0 and 2 in order, and the total reward will be 4, which is the maximum.</p>
</div>

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

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">rewardValues = [1,6,4,3,2]</span></p>

<p><strong>Output:</strong> <span class="example-io">11</span></p>

<p><strong>Explanation:</strong></p>

<p>Mark the indices 0, 2, and 1 in order. The total reward will then be 11, which is the maximum.</p>
</div>

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

<ul>
	<li><code>1 &lt;= rewardValues.length &lt;= 5 * 10<sup>4</sup></code></li>
	<li><code>1 &lt;= rewardValues[i] &lt;= 5 * 10<sup>4</sup></code></li>
</ul>

from sortedcontainers import SortedList, SortedSet


class Solution:
    def maxTotalReward(self, rewardValues: List[int]) -> int:
        uniqVals = set(rewardValues)
        hi = max(uniqVals)
        sl = SortedList()
        sl2 = SortedList(uniqVals)
        arr = []
        chosen = [False] * (hi + 1)
        for i in range(1, hi + 1):
            if i not in uniqVals:
                sl.add(i)
            else:
                chosen[i] = True
                arr.append(i)
        # print(arr)
        if len(arr) == 1:
            return arr[0]
        if len(sl) == 0 or sl[-1] < hi - 1:
            return hi + hi - 1
        arr.sort()
        for x in arr:
            if x == arr[0]:
                continue
            tempind = sl2.bisect_right(min(x-1, hi - 1 - x)) - 1
            if tempind <= 100:
                for i in range(tempind+1):
                    val = sl2[i] + x
                    chosen[val] = True
                    sl2.add(val)
                    sl.discard(val)
                continue


            leftval = sl2[tempind]

            top = x + leftval
            ind = sl.bisect_right(top) - 1
            for i in range(ind, -1, -1):
                val = sl[i]
                if val <= x:
                    break
                comp = val - x
                if chosen[comp]:
                    if val == hi - 1:
                        return 2 * hi - 1
                    chosen[val] = True
                    sl2.add(val)
                    sl.pop(i)
                ind -= 1
        for i in range(hi - 1, -1, -1):
            if chosen[i]:
                return hi + i
        return -1

26000