Crazy Diamond

You are given a permutation $p$ of integers from $1$ to $n$, where $n$ is an even number. Your goal is to sort the permutation. […]