<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)
        #sl = [-1,n]
        sl = SortedList([-1, n])
        prefix = list(accumulate(nums, initial=0))
        mp = {-1 : n}
        pq = [(-prefix[-1], -1, n)]
        
        ans = []
        for q in removeQueries: 
            """
            insertInd = bisect_left(sl,q)
            sl.insert(insertInd, q)
            i = bisect_left(sl,q)
            """
            sl.add(q)
            i = sl.bisect_left(q)


            #print(sl, i)
            lo = sl[i-1]
            hi = sl[i+1]
            mp[lo] = q
            mp[q] = hi 
            heappush(pq, (-(prefix[q]-prefix[lo+1]), lo, q))
            heappush(pq, (-(prefix[hi]-prefix[q+1]), q, hi))
            
            while mp[pq[0][1]] != pq[0][2]: heappop(pq)
            ans.append(-pq[0][0])
        return ans 







    def maximumSegmentSumKD(self, nums: List[int], removeQueries: List[int]) -> List[int]:
        

        #prefix + maxHeap
        #create heap with sum + interval
        #create a stack of remove queries that need to be checked and applied/removed
        N = len(nums)
        P = list(accumulate(nums,lambda x,y:x+y))   #with P[-1] = 0 (-1 doesnt mean last)

        maxHeap = [(-P[-1],(0,N-1))]
        toRemove = deque([])
        res = []

        for q in removeQueries:
            #either r affects the maxValue
            #print("Before", q, maxHeap)
            toRemove.appendleft(q)

            size = len(toRemove)

            for i in range(size):
            #while toRemove:
                r = toRemove.popleft()
        
                a,b = maxHeap[0][1]
                if a <= r <= b:
                    _ = heapq.heappop(maxHeap)

                    #[a,r)
                    B = P[r-1] if r > 0 else 0
                    A = P[a-1] if a > 0 else 0

                    if B-A > 0:
                        heapq.heappush(maxHeap, ( -(B - A), (a,r-1)))

                    B = P[b]
                    A = P[r] #if r < N-1 else P[b]
                    if B - A > 0:
                        heapq.heappush(maxHeap, ( -(B - A), (r+1,b)))

                    #break

                else:
                    toRemove.append(r)

            if maxHeap:
                res.append(-maxHeap[0][0])
            else:
                res.append(0)

            #print("After", r, maxHeap)


        return res
1510