The suggestion of Karl Waugh can be fixed. Let us call a permutation nice if it satisfies the conditions of the problem. Let $a_0 a_1\cdots a_{2n}$ be a permutation of $V_n$. There are six possible orderings of the numbers $a_0, a_1, a_2$, all equally likely. Two of these orderings are incompatible with niceness, so there is a $2/3$ probability of compatibility. Similarly there is a $2/3$ probability, independent from the values of $a_0,a_1,a_2$, that $a_3,a_4,a_5$ are compatible with niceness. Continuing this argument gives an upper bound of $(2/3)^{\lfloor (2n+1)/3\rfloor}\to 0$ on the probability for a permutation of $0,1,\dots,2n$ to be nice.

A further thought. Alternating permutations are nice. The number $E_n$ of alternating permutations of $1,2,\dots,n$ (an Euler number) satisfies $E_n\sim C(2/\pi)^nn!$. If $f(2n+1)$ denotes the number of nice permutations of $V_n$, then this suggests that the limit $$ L=\lim_{n\to \infty} \left( \frac{f(2n+1)}{(2n+1)!}\right)^{1/(2n+1)} $$ exists. The observations above show that then $$ \frac{2}{\pi}=0.6366\cdots \leq L\leq\left(\frac 23\right)^{1/3}= 0.8735\cdots. $$ It would be interesting to determine this limit. The upper bound can be made arbitrary close to $L$ by looking at blocks of length $k$ (rather than of length three) as $k\to\infty$.

The suggestion of Karl Waugh can be fixed. Let us call a permutation nice if it satisfies the conditions of the problem. Let $a_0 a_1\cdots a_{2n}$ be a permutation of $V_n$. There are six possible orderings of the numbers $a_0, a_1, a_2$, all equally likely. Two of these orderings are incompatible with niceness, so there is a $2/3$ probability of compatibility. Similarly there is a $2/3$ probability, independent from the values of $a_0,a_1,a_2$, that $a_3,a_4,a_5$ are compatible with niceness. Continuing this argument gives an upper bound of $(2/3)^{\lfloor (2n+1)/3\rfloor}\to 0$ on the probability for a permutation of $0,1,\dots,2n$ to be nice.

A further thought. Alternating permutations are nice. The number $E_n$ of alternating permutations of $1,2,\dots,n$ (an Euler number) satisfies $E_n\sim C(2/\pi)^nn!$. If $f(2n+1)$ denotes the number of nice permutations of $V_n$, then this suggests that the limit $$ L=\lim_{n\to \infty} \left( \frac{f(2n+1)}{(2n+1)!}\right)^{1/(2n+1)} $$ exists. The observations above show that then $$ \frac{2}{\pi}=0.6366\cdots \leq L\leq\left(\frac 23\right)^{1/3}= 0.8735\cdots. $$ It would be interesting to determine this limit. The upper bound can be made arbitrary close to $L$ by looking at blocks of length $k$ (rather than of length three) as $k\to\infty$. Doing it for $k=10$ yields (modulo computational error) an upper bound of $L\leq (405581/10!)^{1/5} = 0.64515\cdots$.

The suggestion of Karl Waugh can be fixed. Let us call a permutation nice if it satisfies the conditions of the problem. Let $a_0 a_1\cdots a_{2n}$ be a permutation of $V_n$. There are six possible orderings of the numbers $a_0, a_1, a_2$, all equally likely. Two of these orderings are incompatible with niceness, so there is a $2/3$ probability of compatibility. Similarly there is a $2/3$ probability, independent from the values of $a_0,a_1,a_2$, that $a_3,a_4,a_5$ are compatible with niceness. Continuing this argument gives an upper bound of $(2/3)^{\lfloor (2n+1)/3\rfloor}\to 0$ on the probability for a permutation of $0,1,\dots,2n$ to be nice.

The suggestion of Karl Waugh can be fixed. Let us call a permutation nice if it satisfies the conditions of the problem. Let $a_0 a_1\cdots a_{2n}$ be a permutation of $V_n$. There are six possible orderings of the numbers $a_0, a_1, a_2$, all equally likely. Two of these orderings are incompatible with niceness, so there is a $2/3$ probability of compatibility. Similarly there is a $2/3$ probability, independent from the values of $a_0,a_1,a_2$, that $a_3,a_4,a_5$ are compatible with niceness. Continuing this argument gives an upper bound of $(2/3)^{\lfloor (2n+1)/3\rfloor}\to 0$ on the probability for a permutation of $0,1,\dots,2n$ to be nice.

A further thought. Alternating permutations are nice. The number $E_n$ of alternating permutations of $1,2,\dots,n$ (an Euler number) satisfies $E_n\sim C(2/\pi)^nn!$. If $f(2n+1)$ denotes the number of nice permutations of $V_n$, then this suggests that the limit $$ L=\lim_{n\to \infty} \left( \frac{f(2n+1)}{(2n+1)!}\right)^{1/(2n+1)} $$ exists. The observations above show that then $$ \frac{2}{\pi}=0.6366\cdots \leq L\leq\left(\frac 23\right)^{1/3}= 0.8735\cdots. $$ It would be interesting to determine this limit. The upper bound can be made arbitrary close to $L$ by looking at blocks of length $k$ (rather than of length three) as $k\to\infty$.