Time complexity of the fastest algorithm for this case

Question

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(nlogn)$ but not $O(n)$
B.$O(n)$ but not $O(\sqrt{n})$
C.$O(\sqrt{n})$ but not $O(logn)$
D.$O(logn)$ but not $O(1)$
E.$ O(1)$

My approach:
1.Pair wise swapping can be done which will result in $O(n)$
2.Starting from the left every even position from the start will be swapped with the even position from the right
1 2 3 4 5 6 7 8 -- 2 will be swapped with 7 similarly 4 and 5
odd length can be also listed which is taking $n/4$ steps
So i want to confirm whether only $O(n)$ is the max can best algorithm can be achieved or better can be achieved.

Answer 1

I think it's not optimal but here's a lower bound: you have to move at least $\lfloor\frac{n}{3}\rfloor$ elements.

Split $A$ into blocks of 3ドル$: {$A[1],A[2],A[3]$}, {$A[4],A[5],A[6]$}, ...

The claim is you have to move at least one element from each block. Otherwise, assume the block {$A[k],A[k+1],A[k+2]$} is kept unchanged. Since $A$ is sorted, $\min(A[k],A[k+2])<A[k+1]<\max(A[k],A[k+2]),ドル which violates your constraint. So the problem takes $\Omega(n)$. Combine this with your $O(n)$ approach we get $\Theta(n)$.