<p>You are given two <strong>0-indexed</strong> integer arrays <code>nums</code> and <code>removeQueries</code>, both of length <code>n</code>. For the <code>i<sup>th</sup></code> query, the element in <code>nums</code> at the index <code>removeQueries[i]</code> is removed, splitting <code>nums</code> into different segments.</p>

<p>A <strong>segment</strong> is a contiguous sequence of <strong>positive</strong> integers in <code>nums</code>. A <strong>segment sum</strong> is the sum of every element in a segment.</p>

<p>Return<em> an integer array </em><code>answer</code><em>, of length </em><code>n</code><em>, where </em><code>answer[i]</code><em> is the <strong>maximum</strong> segment sum after applying the </em><code>i<sup>th</sup></code> <em>removal.</em></p>

<p><strong>Note:</strong> The same index will <strong>not</strong> be removed more than once.</p>

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

<pre>
<strong>Input:</strong> nums = [1,2,5,6,1], removeQueries = [0,3,2,4,1]
<strong>Output:</strong> [14,7,2,2,0]
<strong>Explanation:</strong> Using 0 to indicate a removed element, the answer is as follows:
Query 1: Remove the 0th element, nums becomes [0,2,5,6,1] and the maximum segment sum is 14 for segment [2,5,6,1].
Query 2: Remove the 3rd element, nums becomes [0,2,5,0,1] and the maximum segment sum is 7 for segment [2,5].
Query 3: Remove the 2nd element, nums becomes [0,2,0,0,1] and the maximum segment sum is 2 for segment [2]. 
Query 4: Remove the 4th element, nums becomes [0,2,0,0,0] and the maximum segment sum is 2 for segment [2]. 
Query 5: Remove the 1st element, nums becomes [0,0,0,0,0] and the maximum segment sum is 0, since there are no segments.
Finally, we return [14,7,2,2,0].</pre>

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

<pre>
<strong>Input:</strong> nums = [3,2,11,1], removeQueries = [3,2,1,0]
<strong>Output:</strong> [16,5,3,0]
<strong>Explanation:</strong> Using 0 to indicate a removed element, the answer is as follows:
Query 1: Remove the 3rd element, nums becomes [3,2,11,0] and the maximum segment sum is 16 for segment [3,2,11].
Query 2: Remove the 2nd element, nums becomes [3,2,0,0] and the maximum segment sum is 5 for segment [3,2].
Query 3: Remove the 1st element, nums becomes [3,0,0,0] and the maximum segment sum is 3 for segment [3].
Query 4: Remove the 0th element, nums becomes [0,0,0,0] and the maximum segment sum is 0, since there are no segments.
Finally, we return [16,5,3,0].
</pre>

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

<ul>
	<li><code>n == nums.length == removeQueries.length</code></li>
	<li><code>1 &lt;= n &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= nums[i] &lt;= 10<sup>9</sup></code></li>
	<li><code>0 &lt;= removeQueries[i] &lt; n</code></li>
	<li>All the values of <code>removeQueries</code> are <strong>unique</strong>.</li>
</ul>

from sortedcontainers import SortedList
class Solution:
    def maximumSegmentSum(self, nums: List[int], removeQueries: List[int]) -> List[int]:
        n = len(nums)
        prefix = []
        prefix_sum = 0

        for num in nums:
            prefix.append(prefix_sum + num)
            prefix_sum = prefix[-1]
        
        def is_decomissioned(heap_range):
            _, l, r = heap_range
            if l > r:
                return True

            index_for_r = removedIndices.bisect_left(r)

            # print(f"\tchecking {l}, {r} with {index_for_r}, --> {removedIndices} -->")
            if (index_for_r >= 0 and  index_for_r < len(removedIndices) and removedIndices[index_for_r] == r):
                return True

            if index_for_r == 0:
                return False

            # print(f"\t{l <= removedIndices[index_for_r - 1]}")
            return l <= removedIndices[index_for_r - 1]

        def range_sum(l, r):
            if r<l:
                return 0

            if l <= 0:
                return prefix[r]

            return prefix[r] - prefix[l-1]
        
        def get_left_right_removedIndices(index):
            left, right = removedIndices.bisect_left(index) - 1, removedIndices.bisect_left(index)
            # print(f"{left} {right}")
            l = removedIndices[left] if left >= 0 else -1 
            r = removedIndices[right] if right < len(removedIndices) else n
            # print(f"{removedIndices} --> {index} --> {l}, {r}")
            return l, r

        heap = [(-sum(nums) ,0, n-1)]

        removedIndices = SortedList()
        answer = []
        for index in removeQueries:
            l, r =  get_left_right_removedIndices(index)
            removedIndices.add(index)
            right_range = (-range_sum(index + 1, r-1), index+1, r-1)
            left_range = (-range_sum(l+1, index - 1), l+1, index-1)
            heapq.heappush(heap, left_range)
            heapq.heappush(heap, right_range)
            # print(heap)
            # print()
            while heap and is_decomissioned(heap[0]):
                heapq.heappop(heap)
            
                
            answer.append(-heap[0][0] if heap else 0)

        return answer

        
56300