The answer is Yes. Let me first reformulate the problem. For a given permutation $(a_1,a_2,\dots,a_{2n+1})$, we construct a 2-colored graph $G$ on vertices $[2n+1]:=\{1,2,\dots,2n+1\}$ formed by black edges $\{i,i+1\}$ and gray edges $\{a_i,a_{i+1}\}$ for $i\in [2n+1]$ with $2n+2\equiv 1$. Hence, $G$ is the superposition of the black and gray cycles, each of length $2n+1$. The question is equivalent to finding a labeling of the vertices of $G$ with labels from $\{A,B\}$, imposing the edge labels from $\{AA,AB,BB\}$ formed by the labels of edge's endpoints, such that there are no two adjacent black edges both labeled $AA$, and there are no two adjacent gray edges both labeled $BB$. We call such pairs of adjacent labeled edges *forbidden*. Let us show that the required labeling exists for any $n\geq 2$. We construct graph $G'$ from $G$ by first removing vertex $1$ with its incident edges, which we refer to as *special*. Then we further remove black edges $\{3,4\}$, $\{5,6\}$, ..., $\{2n-1,2n\}$, and gray edges $\{a_{s+2},a_{s+3}\}$, $\{s_{s+4},a_{s+5}\}$, ..., $\{a_{s+2n-2},a_{s+2n-1}\}$, where $s:=a^{-1}(1)$, i.e. $a_s=1$. In other words, we remove every other edge along the black path and every other edge along the gray path. We refer to these removed edges as *bridges* in $G$, and to the remaining edges (i.e., the edges in $G'$) as *basic*. In the graph $G'$, every vertex is incident to one black and one gray edge, and so $G'$ is the disjoint union of alternating cycles of even length. We label vertices along each such cycle alternatively with $A$'s and $B$'s starting at an arbitrary vertex, except for the cycle containing vertex $2$, which we label with $B$. Hence, all edges of $G'$ inherit label $AB$ from their endpoints. We propagate the vertex labeling from $G'$ to $G$, additionally labeling vertex $1$ with $A$. Each basic edge in $G$ has label $AB$ and thus it cannot participate in a forbidden pair. So, if a forbidden pair exists, it is formed by bridges and/or special edges. However, a bridge $e$ cannot participate in a forbidden pair since its adjacent edges of the same color as $e$ are basic. It remains to notice that two special edges cannot form a forbidden pair either, since the black special edge $(1,2)$ has label $AB$, while the labels of gray special edges are either $AA$ and $AB$ (since vertex $1$ has label $A$). QED PS. Graphs like $G$ are known under the name of (unsigned) [breakpoint graphs](https://en.wikipedia.org/wiki/Sequence_graph).