Runtime analysis of sorting an array with known number of inversions I'm having difficulties with analyzing the worst-case runtime of this following case:

I'm given an array that has $n$ natural numbers. Out of all $\binom{n}{2} = \frac{n(n-1)}{2}$ possible pairs there are $\frac{n(n-1)}{2} - 5n$ inversions. Inversion is defined like this: $a[i] &lt; a[j],\ i&gt;j$. 

So of course you can sort the array in $O(n \log n)$ time but can you do any better than this? I've looked online and saw that inversion sort time is in $\Theta(n+I)$ where $I= \text{# inversions}$ but then I get that $I=\Theta(n^2)$ so it doesn't really help me.
Hint: Make use of the following facts:


Each pair $i,j$ that forms an inversion for sorting in ascending order, does not form an inversion when sorting in descending order (and vice versa).
Reversing the complete list can be done in $\Theta(n)$.