### Problem Setting

Given a sequence of integers with a length n,compute the number of reverse pairs in the sequence.

### Reverse Pair

For the i-th and j-th element in the sequence a, if it meets the condition that i < j and a[i] > a[j], then it is a reverse pair; otherwise it’s not.

### Data Range

$1 \leq n \leq 100000$

e.g.

### Output

number of reverse order pairs, e.g.

### Analysis

• Here we use quick sort to approach this problem. The connection between this problem and the original quick sort is that when we do the sorting and q[i] > q[j] (we assume i<j), we are supposed to select q[j] as the next element in the sorted array. At the same time, it is worth noting that we have found mid-i+1 reverse pairs. Because all of the elements, from q[i] to q[mid], form reverse pairs with q[j].
• If the input number is large, we’d better use long long for the count variable.