1
from sortedcontainers import SortedList
2

3

4
class Solution:
5
    """
6
    For each sub array nums[0, i]
7
    We sum the reverse pairs count
8
    of x, s.t x in [0, i-1] and nums[x] >= 2 * nums[i] + 1
9
    Using a BST(sortedList) to get logN insert and lookup time.
10
    Time: O(NlogN)
11
    Space: O(N)
12
    """
13

14
    def reversePairs(self, nums: List[int]) -> int:
15
        res = 0
16
        bst = SortedList()
17
        for e in nums:
18
            res += len(bst) - bst.bisect_left(2 * e + 1)  # the count is the N - index
19
            bst.add(e)  # add the the bst
20
        return res