As a hint - the runtime of insertion sort is Θ(n + I), where n is the number of elements and I is the number of inversions in the array. What happens if you insertion sort the array, given that it only has O(n) inversions? What will the time complexity be?
Hope this helps!