116. Reverse Pairs

Given an integer array nums, return the number of reverse pairs — pairs (i,j) where 0<=i<j<=n-1 and nums[i] > 2 * nums[j].

Input: Integer array nums.

Output: Integer — count of reverse pairs.

Examples

Example 1

Input: [1,3,2,3,1]
Output: 2
Explanation: (1,4): 3>2*1=2. (3,4): 3>2*1=2. Count=2.

Example 2

Input: [2,4,3,5,1]
Output: 3
Explanation: (0,4): 2>2. No. (1,4): 4>2. (2,4): 3>2. (3,4): 5>2. Count=3.

Example 3

Input: [1,2,3,4,5]
Output: 0
Explanation: No reverse pairs.