<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:
        pass
























from sortedcontainers import SortedList
class Solution:
    def reversePairs(self, nums: List[int]) -> int:
        sl = SortedList()
        cnt = 0
        for num in nums:
            idx = sl.bisect_right(num*2)
            cnt += len(sl) - (idx)
            sl.add(num)
        return cnt







class Solution:
    def reversePairs(self, nums: List[int]) -> int:
        self.count = 0
        self.merge_sort_and_count(nums, 0, len(nums)-1)
        return self.count

    def merge_sort_and_count(self, nums, p1, p2):
        if p1 >= p2:
            return
        pm = (p1 + p2) // 2
        self.merge_sort_and_count(nums, p1, pm)
        self.merge_sort_and_count(nums, pm+1, p2)
        self.check_count(nums, p1, pm, p2)
        self.merge_sort(nums, p1, pm, p2)

    def check_count(self, nums, p1, pm, p2):
        l1, l2 = p1, pm+1
        while l1 <= pm:
            while l2 <= p2 and nums[l1] > 2 * nums[l2]:  # Edited: Corrected the loop to count all valid pairs
                l2 += 1
            self.count += l2 - (pm + 1)  # Edited: Count all valid pairs for nums[l1]
            l1 += 1
        
    def merge_sort(self, nums, p1, pm, p2):
        l1, l2 = p1, pm+1
        merged = []
        while l1 <= pm and l2 <= p2:
            if nums[l1] <= nums[l2]:
                merged.append(nums[l1])
                l1 += 1
            else:
                merged.append(nums[l2])
                l2 += 1
        
        while l1 <= pm:
            merged.append(nums[l1])
            l1 += 1

        while l2 <= p2:
            merged.append(nums[l2])
            l2 += 1
        
        nums[p1:p2+1] = merged




























class Solution:
    def reversePairs(self, nums: List[int]) -> int:
        sl = SortedList()
        cnt = 0
        for num in nums:
            idx = sl.bisect_right(num * 2)
            # idx: index of rightmost value that meets num*2 < sl[idx]
            # idx: number of nums in sl that is smaller or equal to num*2
            cnt += len(sl) - idx
            sl.add(num)
        return cnt



class Solution:
    def reversePairs(self, nums: List[int]) -> int:
        self.cnt = 0
        self.merge_sort_and_count(nums, 0, len(nums)-1)
        return self.cnt

    def merge_sort_and_count(self, nums, p1, p2):
        if p1 >= p2:
            return 
        pm = (p1 + p2) // 2
        self.merge_sort_and_count(nums, p1, pm)
        self.merge_sort_and_count(nums, pm+1, p2)
        self.count(nums, p1, pm, p2)

        l1, l2 = p1, pm+1
        merged = []
        while l1 <= pm and l2 <= p2:
            if nums[l1] <= nums[l2]:
                merged.append(nums[l1])
                l1 += 1
            else:
                merged.append(nums[l2])
                l2 += 1
        
        while l1 <= pm:
            merged.append(nums[l1])
            l1 += 1
        while l2 <= p2:
            merged.append(nums[l2])
            l2 += 1
        
        nums[p1:p2+1] = merged

    def count(self, nums, p1, pm, p2):
        # nums[p1:pm+1] and nums[pm+1:p2] are sorted respectively. 
        l1 = p1
        l2 = pm+1
        while l1 <= pm:
            while l2 <= p2 and nums[l1] > nums[l2] * 2:
                l2 += 1
            self.cnt += (l2-1) - (pm+1) + 1
            l1 += 1


















# 1,2, 3, 4, 5, 5, 5, 6, 7

from sortedcontainers import SortedList

class Solution:
    def reversePairs(self, nums: List[int]) -> int:
        sl = SortedList()
        ans = 0
        for i in range(len(nums)):
            idx_found = sl.bisect_right(nums[i]*2)
            ans += (len(sl) - idx_found)
            sl.add(nums[i])
        return ans


class Solution:
    def reversePairs(self, nums: List[int]) -> int:
        self.cnt = 0
        self.nums = nums
        self.merge_sort_and_count(0, len(nums)-1)
        return self.cnt

    def merge_sort_and_count(self, p1, p2):
        if p1 >= p2:
            return
        pm = (p1 + p2) // 2
        self.merge_sort_and_count(p1, pm)
        self.merge_sort_and_count(pm+1, p2)
        self.count(p1, pm, p2)

        l1 = p1
        l2 = pm+1
        merged = []
        while l1 <= pm and l2 <= p2:
            if self.nums[l1] <= self.nums[l2]:
                merged.append(self.nums[l1])
                l1 += 1
            else:
                merged.append(self.nums[l2])
                l2 += 1
        while l1 <= pm:
            merged.append(self.nums[l1])
            l1 += 1
        while l2 <= p2:
            merged.append(self.nums[l2])
            l2 += 1
        self.nums[p1:p2+1] = merged

    def count(self, p1, pm, p2):
        l1 = p1
        l2 = pm + 1
        while l1 <= pm:
            while l2 <= p2 and self.nums[l1] > 2 * self.nums[l2]:
                l2 += 1
            self.cnt += (l2-1 - (pm+1) + 1)
            l1 += 1


























from sortedcontainers import SortedList

class Solution:
    def reversePairs(self, nums: List[int]) -> int:
        sl = SortedList()
        cnt = 0
        for j in range(len(nums)):
            idx = sl.bisect_right(nums[j] * 2)
            cnt += len(sl)-1 - idx + 1
            sl.add(nums[j])
        return cnt


class Solution:
    def reversePairs(self, nums: List[int]) -> int:
        self.cnt = 0
        self.nums = nums
        self.merge_sort_and_count(0, len(nums)-1)
        return self.cnt
    
    def merge_sort_and_count(self, p1, p2):
        if p1 >= p2:
            return 
        pm = (p1 + p2) // 2
        self.merge_sort_and_count(p1, pm)
        self.merge_sort_and_count(pm+1, p2)
        self.count(p1, pm, p2)

        l1 = p1
        l2 = pm + 1
        merged = []
        while l1 <= pm and l2 <= p2:
            if self.nums[l1] <= self.nums[l2]:
                merged.append(self.nums[l1])
                l1 += 1
            else:
                merged.append(self.nums[l2])
                l2 += 1
        while l1 <= pm:
            merged.append(self.nums[l1])
            l1 += 1
        while l2 <= p2:
            merged.append(self.nums[l2])
            l2 += 1
        self.nums[p1:p2+1] = merged
    
    def count(self, p1, pm, p2):
        l1 = p1
        l2 = pm+1
        while l1 <= pm:
            while l2 <= p2 and self.nums[l1] > 2 * self.nums[l2]:
                l2 += 1
            self.cnt += (l2-1) - (pm+1) + 1
            l1 += 1























class Solution:
    def reversePairs(self, nums: List[int]) -> int:
        self.cnt = 0
        self.nums = nums
        self.merge_sort_and_count(0, len(nums)-1)
        return self.cnt

    def merge_sort_and_count(self, p1, p2):
        if p1 >= p2:
            return 
        pm = (p1 + p2) // 2
        self.merge_sort_and_count(p1, pm)
        self.merge_sort_and_count(pm+1, p2)
        self.count(p1, pm, p2)

        l1, l2 = p1, pm + 1
        merged = []
        while l1 <= pm and l2 <= p2:
            if self.nums[l1] <= self.nums[l2]:
                merged.append(self.nums[l1])
                l1 += 1
            else:
                merged.append(self.nums[l2])
                l2 += 1
        while l1 <= pm:
            merged.append(self.nums[l1])
            l1 += 1
        while l2 <= p2:
            merged.append(self.nums[l2])
            l2 += 1
        self.nums[p1:p2+1] = merged

    def count(self, p1, pm, p2):
        '''
        p1~pm, pm+1~p2 are sorted
        '''
        i, j = p1, pm+1
        while i <= pm:
            while j <= p2 and self.nums[i] > 2 * self.nums[j]:
                j += 1    
            self.cnt += j - (pm+1)
            i += 1
        




















class Solution:
    def reversePairs(self, nums: List[int]) -> int:
        self.nums = nums
        self.cnt = 0
        self.merge_sort_and_count(0, len(nums)-1)
        return self.cnt
    
    def merge_sort_and_count(self, p1, p2):
        if p1 >= p2:
            return 
        pm = (p1 + p2)//2
        self.merge_sort_and_count(p1, pm)
        self.merge_sort_and_count(pm+1, p2)
        self.count(p1, pm, p2)
        
        merged = []
        l1, l2 = p1, pm + 1
        while l1 <= pm and l2 <= p2:
            if self.nums[l1] < self.nums[l2]:
                merged.append(self.nums[l1])
                l1 += 1
            else:
                merged.append(self.nums[l2])
                l2 += 1
        while l1 <= pm:
            merged.append(self.nums[l1])
            l1 += 1
        while l2 <= p2:
            merged.append(self.nums[l2])
            l2 += 1
        self.nums[p1:p2+1] = merged
            
    def count(self, p1, pm, p2):
        # nums[i] > 2 * nums[j]
        j = pm + 1
        for i in range(p1, pm+1):
            while j <= p2 and self.nums[i] > 2 * self.nums[j]:
                j += 1
            self.cnt += (j-1) - (pm+1) + 1
    




















class Solution:
    def reversePairs(self, nums: List[int]) -> int:
        self.nums = nums
        self.cnt = 0
        self.merge_sort_and_count(0, len(nums)-1)
        return self.cnt
    
    def merge_sort_and_count(self, p1, p2):
        if p1 >= p2:
            return 
        pm = (p1 + p2)//2
        self.merge_sort_and_count(p1, pm)
        self.merge_sort_and_count(pm+1, p2)
        self.count(p1, pm, p2)
        
        merged = []
        l1, l2 = p1, pm + 1
        while l1 <= pm and l2 <= p2:
            if self.nums[l1] < self.nums[l2]:
                merged.append(self.nums[l1])
                l1 += 1
            else:
                merged.append(self.nums[l2])
                l2 += 1
        while l1 <= pm:
            merged.append(self.nums[l1])
            l1 += 1
        while l2 <= p2:
            merged.append(self.nums[l2])
            l2 += 1
        self.nums[p1:p2+1] = merged

    def count(self, p1, pm, p2):
        # nums[i] > 2 * nums[j]
        l2 = pm + 1
        for l1 in range(p1, pm+1):
            while l2 <= p2 and self.nums[l1] > 2 * self.nums[l2]:
                l2 += 1
            self.cnt += (l2-1 - (pm + 1) + 1)
24800