Given a list of distinct positive integers \((a_0,\ldots,a_{n-1})\). An inversion is a pair \(i<j\) where \(a_i>a_j\).

Design and implement a \(\Theta(n\, \log n)\) algorithm that counts all inversions in a given row.

Assignment

Write a Python function countInversions(numbers: list) that returns the number of inversions in a given list of numbers.

Examples

>>> countInversions([2, 4, 3, 1, 5])
4
>>> countInversions([0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10])
0
>>> countInversions([10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0])
55