For odd $n$ the answer to your question (as stated!) can be found in Noga Alon's paper. Namely, the number of permutations in your question equals the permanent of an $n\times n$ matrix $A$ in which each row and each column has $(n-1)/2$ ones and $(n+1)/2$ zeros. Therefore $2/(n-1)*A$ is doubly stochastic, so by van der Waerden's conjecture (proved by Egorichev and Falikman in 1981) the requested probability is $\geq n!^{-1}((n-1)/2)^n n!/n^n=(1/e+o(1))2^{-n}$.

For even $n$ the answer is similar. Then the number of permutations in your question equals the permanent of an $n\times n$ matrix $A$ in which each row and each column has $n/2$ ones and $n/2$ zeros. Therefore $2/n*A$ is doubly stochastic, so similarly as before the requested probability is $\geq n!^{-1}(n/2)^n n!/n^n=2^{-n}$.

On the other hand, for all $n$ the considered permanent is $\ll \sqrt{n} n!/2^n$ by Noga Alon's main theorem in the paper, hence the requested probability is $\ll \sqrt{n}2^{-n}$.

Of course this does not explain why (3.1) in Noga Alon's paper holds. This is a statement about random *cyclic permutations* $\pi$ satisfying $\pi(i+1)−\pi(i) \mod{n} < n/2$ for all $i$.