Anti Adjacent Swaps

You are given an array $A$ of $N$ elements. In one operation you can swap any two elements if they are **not** adjacent. That is, you can pick two indices $i$ and $j$ ($1 \leq i \lt j \leq N$) such that $j-i\gt 1$, and swap $A_i$ and $A_j$. Using this operation finitely many (possibly, zero) times, is it possible to turn $A$ into a sorted array? ### Input - The first line of input will contain