956. Count Inversions Using BIT

Given an integer array, return the number of inversions — pairs of indices (i, j) with i < j and nums[i] > nums[j]. Use a Binary Indexed Tree over compressed ranks (or a merge sort). The input is a JSON array.

Input: A JSON array of integers.

Output: Integer — the number of inversions.

Examples

Input: [8,4,2,1]
Output: 6
Explanation: Every pair is inverted.

Input: [1,2,3]
Output: 0
Explanation: Already sorted.

Input: [2,1]
Output: 1
Explanation: One inversion.

Constraints

• 0<=n<=10^5
• -10^9<=value<=10^9

Asked by