<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]:
        segments = SortedList([(0, len(nums))])
        st = ST(nums, init=True)
        sums = SortedList([st[:]])
        res = []
        for query in removeQueries:
            idx = segments.bisect_left((query, inf)) - 1
            start, end = segments[idx]
            s1, s2 = st[start:query], st[query+1: end]
            total_sum = st[start:end]
            sums.discard(total_sum)
            sums.add(s1)
            sums.add(s2)
            del segments[idx]
            segments.add((start, query))
            segments.add((query + 1, end))
            res.append(sums[-1] if sums else 0)
        return res

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
52000