递归构造，为了方便构造，将条件加强：长度为 $2$ 的上升和下降子序列数量也要相同。

设长度为 $n - 4$ 的答案为 $a_1, a_2, \cdots, a_{n - 4}$，那么构造长度为 $n$ 的序列 $n - 1, 1, a_1 + 2, a_2 + 2, \cdots, a_{n - 4} + 2, n, 2$，容易验证这个序列也符合条件。

于是按照 $n$ 模 $4$ 的余数分类讨论：

• 若 $n \equiv 0, 1 \pmod 4$，那么按照上述递归构造，最终 $n = 0, 1$ 时均可以直接符合条件；
• 若 $n \equiv 2, 3 \pmod 4$，那么开头两个数放 $1, n$，剩下 $n - 2$ 个位置按照长度为 $n - 2$ 构造，由于长度为 $2$ 的上升和下降子序列数量相同，所以额外的长度为 $3$ 的上升和下降子序列数量也相同。