An array of n distinct elements is said to be un-sorted if for every index i such that 2 ≤ i ≤ n − 1, either A[i] > max{A[i − 1], A[i + 1]}, or A[i] < min{A[i − 1], A[i + 1]}.
What is the time-complexity of the fastest algorithm that takes as input a sorted array A with n distinct elements, and un-sorts A?
