534. Reverse Pairs (Modified Merge Sort)

Given an array, count the number of reverse pairs — pairs of indices (i, j) with i < j and nums[i] > 2 * nums[j]. Use a modified merge sort. Input: an array of integers.

Input: An array of integers.

Output: Integer — the number of reverse pairs.

Examples

Input: [1,3,2,3,1]
Output: 2
Explanation: Pairs (3,1) and (3,1) qualify.

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

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

Constraints

• 1<=n<=5*10^4
• -2^31<=value<=2^31-1

Asked by