枚举第一个数的奇偶性，由 $S$ 推出整条排列的奇偶性序列。若奇偶数量与 $1 \dots n$ 中奇偶数数量一致，则用最小可用奇数/偶数依次填入。两个起点都可行时取字典序更小者。