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$?
$(A) O(n log n)$ but not $O(n)$
$(B) O(n)$ but not $O( \sqrt{n})$
$(C) O( \sqrt{n})$ but not $O(log n)$
$(D) O(log n)$ but not $O(1)$
