<p>You are given a <strong>0-indexed</strong> array of <strong>positive</strong> integers <code>nums</code>.</p>

<p>A subarray of <code>nums</code> is called <strong>incremovable</strong> if <code>nums</code> becomes <strong>strictly increasing</strong> on removing the subarray. For example, the subarray <code>[3, 4]</code> is an incremovable subarray of <code>[5, 3, 4, 6, 7]</code> because removing this subarray changes the array <code>[5, 3, 4, 6, 7]</code> to <code>[5, 6, 7]</code> which is strictly increasing.</p>

<p>Return <em>the total number of <strong>incremovable</strong> subarrays of</em> <code>nums</code>.</p>

<p><strong>Note</strong> that an empty array is considered strictly increasing.</p>

<p>A <strong>subarray</strong> is a contiguous non-empty sequence of elements within an array.</p>

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

<pre>
<strong>Input:</strong> nums = [1,2,3,4]
<strong>Output:</strong> 10
<strong>Explanation:</strong> The 10 incremovable subarrays are: [1], [2], [3], [4], [1,2], [2,3], [3,4], [1,2,3], [2,3,4], and [1,2,3,4], because on removing any one of these subarrays nums becomes strictly increasing. Note that you cannot select an empty subarray.
</pre>

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

<pre>
<strong>Input:</strong> nums = [6,5,7,8]
<strong>Output:</strong> 7
<strong>Explanation:</strong> The 7 incremovable subarrays are: [5], [6], [5,7], [6,5], [5,7,8], [6,5,7] and [6,5,7,8].
It can be shown that there are only 7 incremovable subarrays in nums.
</pre>

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

<pre>
<strong>Input:</strong> nums = [8,7,6,6]
<strong>Output:</strong> 3
<strong>Explanation:</strong> The 3 incremovable subarrays are: [8,7,6], [7,6,6], and [8,7,6,6]. Note that [8,7] is not an incremovable subarray because after removing [8,7] nums becomes [6,6], which is sorted in ascending order but not strictly increasing.
</pre>

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

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


from typing import List
from functools import cache


def comprise(nums: List[int]) -> List[int]:
    alt_to_num = sorted(set(nums))
    num_to_alt = {num: alt for alt, num in enumerate(alt_to_num)}
    return [1 + num_to_alt[num] for num in nums]


# A binary indexed tree (BIT)
class BIT:
    def __init__(self, size: int):
        self.bit = [0] * (size + 1)

    # Add 'diff' to index i
    def add(self, i, diff):
        i += 1

        # Traverse all ancestors and add 'diff'
        while i < len(self.bit):
            # Add 'diff' to current node of BI Tree
            self.bit[i] += diff

            # Update index to that of parent in update View
            i += i & (-i)

    # Returns sum(arr[0:i])
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.bit[i]

            # (i & (-i)) 是 lowest bit
            i -= i & (-i)
        return s

    # Returns sum(arr[i:j])
    def sum_range(self, i, j):
        return self.sum(j) - self.sum(i)


class Solution:
    def incremovableSubarrayCount(self, nums: List[int]) -> int:
        n = len(nums)

        k = n - 1
        while k - 1 >= 0 and nums[k - 1] < nums[k]:
            k -= 1
        # nums[k:] is strictly increasing

        if k == 0:
            return n * (n + 1) // 2

        i = 0
        j = k
        result = 0

        while i < n:
            b = nums[i - 2] if i - 2 >= 0 else -2
            c = nums[i - 1] if i - 1 >= 0 else -1

            if not (b < c):
                break

            while j <= i:
                j += 1

            while j < n and nums[j] <= c:
                j += 1

            # After removing nums[i:j], the rest is increasing
            result += n - j + 1

            i += 1

        return result


717