所有长度为 $n$ 的排列中，$n$ 排在最右侧，且任意相邻元素之差的绝对值都不大于 $2$ 的排列一共有多少种？

*注：“长度为 $n$ 的排列”指将 $1$ 到 $n$ 共 $n$ 个数排成一排，每个数只出现 $1$ 次.