Consider an array of size $n$ with perfectly inversely sorted order. Which of the following is correct about the running times to sort this array (deterministically)?