<p>Given an integer array <code>nums</code>, return <em>the number of <strong>reverse pairs</strong> in the array</em>.</p>

<p>A <strong>reverse pair</strong> is a pair <code>(i, j)</code> where:</p>

<ul>
	<li><code>0 &lt;= i &lt; j &lt; nums.length</code> and</li>
	<li><code>nums[i] &gt; 2 * nums[j]</code>.</li>
</ul>

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

<pre>
<strong>Input:</strong> nums = [1,3,2,3,1]
<strong>Output:</strong> 2
<strong>Explanation:</strong> The reverse pairs are:
(1, 4) --&gt; nums[1] = 3, nums[4] = 1, 3 &gt; 2 * 1
(3, 4) --&gt; nums[3] = 3, nums[4] = 1, 3 &gt; 2 * 1
</pre>

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

<pre>
<strong>Input:</strong> nums = [2,4,3,5,1]
<strong>Output:</strong> 3
<strong>Explanation:</strong> The reverse pairs are:
(1, 4) --&gt; nums[1] = 4, nums[4] = 1, 4 &gt; 2 * 1
(2, 4) --&gt; nums[2] = 3, nums[4] = 1, 3 &gt; 2 * 1
(3, 4) --&gt; nums[3] = 5, nums[4] = 1, 5 &gt; 2 * 1
</pre>

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

<ul>
	<li><code>1 &lt;= nums.length &lt;= 5 * 10<sup>4</sup></code></li>
	<li><code>-2<sup>31</sup> &lt;= nums[i] &lt;= 2<sup>31</sup> - 1</code></li>
</ul>

class Solution:
    def reversePairs(self, nums: List[int]) -> int:
        def bsearch_len(arr, val):
            # return the number of elements where it is more than or  2x val
            # arr is sorted
            f = 2 * val
            l = 0
            r = len(arr) - 1
            while l <= r:
                mid = (l + r) // 2
                if arr[mid] <= f:
                    l = mid + 1
                else:
                    r = mid - 1
            return len(arr) - l, l

        def inversions(arr):
            if len(arr) == 1:
                return 0, arr
            mid = len(arr) // 2
            l_inversions, l_arr = inversions(arr[:mid])
            r_inversions, r_arr = inversions(arr[mid:])

            local_count = l_inversions + r_inversions

            # for r_val in r_arr:
            #     res = bsearch_len(l_arr, r_val)
            #     local_count += res

            sorted_both, reverses = merge(l_arr, r_arr)
            return local_count + reverses, sorted_both
        
        def merge(l_arr, r_arr):
            l = 0 
            r = 0
            res = []
            reverses = 0

            l_cop = l_arr[::]

            for r_val in r_arr:
                cnt, index = bsearch_len(l_cop, r_val)
                l_cop = l_cop[index:]
                reverses += cnt


            while l < len(l_arr) and r < len(r_arr):
                if l_arr[l] < r_arr[r]:
                    res.append(l_arr[l])
                    l += 1
                else:
                    res.append(r_arr[r])
                    r += 1
            if r < len(r_arr):
                res += r_arr[r:]
            if l < len(l_arr):
                res += l_arr[l:]
            return res, reverses
        res =  inversions(nums)
        return res[0]



        
22800