<p>A magician has various spells.</p>

<p>You are given an array <code>power</code>, where each element represents the damage of a spell. Multiple spells can have the same damage value.</p>

<p>It is a known fact that if a magician decides to cast a spell with a damage of <code>power[i]</code>, they <strong>cannot</strong> cast any spell with a damage of <code>power[i] - 2</code>, <code>power[i] - 1</code>, <code>power[i] + 1</code>, or <code>power[i] + 2</code>.</p>

<p>Each spell can be cast <strong>only once</strong>.</p>

<p>Return the <strong>maximum</strong> possible <em>total damage</em> that a magician can cast.</p>

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

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

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

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

<p>The maximum possible damage of 6 is produced by casting spells 0, 1, 3 with damage 1, 1, 4.</p>
</div>

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

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

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

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

<p>The maximum possible damage of 13 is produced by casting spells 1, 2, 3 with damage 1, 6, 6.</p>
</div>

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

<ul>
	<li><code>1 &lt;= power.length &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= power[i] &lt;= 10<sup>9</sup></code></li>
</ul>

class Solution:
    def maximumTotalDamage(self, power: List[int]) -> int:
        '''
        We have input 
        power  10^5 length, So we need O(N) or O(NlogN)
        power[i] 10^9
        We should sort the input as we care about the elements close in value to the power we used
        We need i to denote where in the power we are'''
        power.sort()
        memo = [0] * len(power)
        def helper_duplicates(i, a):
            low,high = i, len(power) -1
            while low <=high:
                mid = (low + high) //2
                if power[mid] == a:
                    low = mid + 1
                else:
                    high = mid -1
            return low
        
        def helper_next(i, a):
            low,high = i, len(power) -1
            while low <=high:
                mid = (low + high) //2
                if power[mid] == a + 2 or power[mid] == a + 1:
                    low = mid + 1
                else:
                    high = mid -1
            return low

        def max_power_at(i):
            if i == len(power):
                return 0
            if memo[i]:
                return memo[i]
            
            take,not_take = 0,0
            #take this
            take = power[i]
            curr = power[i]
            index = i
            #duplicates
            i_next = helper_duplicates(i, take)
            length = i_next - i -1
            curr+= take * length

            i_take = helper_next(i_next, take)
            take = max_power_at(i_take) + curr

            not_take = max_power_at(i_next)

            memo[i] = max(take ,not_take)
            return memo[i]
        
        return max_power_at(0)





        
103864