简要题意.

对排列 $p$，令 $q = (p_1, \dots, p_n, p_n, \dots, p_1)$，称 $p$ 合法当且仅当 $q$ 不存在子结构 $(1,4,2,3)$（即不存在子序列离散化后等于 $(1,4,2,3)$）。
问有多少 $n$ 阶排列是好的。

$n \le 10^9$。

2017 年整式递推远处求值还不普及，所以这应该最多是个线性递推！然后扔进 BM 或者 OEIS，做完了（雾）

设 $f_n$ 为答案，分类讨论转移。

若 $p_1 = n$，则这个位置没用。贡献为 $f_{n-1}$。

若 $p_1 = n-1$，那 $n$ 必须在 $p_2$。贡献为 $f_{n-2}$。

若 $p_1 = 1$，那可以发现必然是 $(1, 2, \dots, n-2, n-1, n)$ 或 $(1, 2, \dots, n-2, n, n-1)$。贡献为 $2$。

若 $p_1 = i \in [3, n-2]$，再讨论 $p_2$：

• 若 $p_2 = 1$，则会有 $(p_2,n,2,p_1)$。
• 若 $p_2 \in [2, i-1]$，则会有 $(1,n,p_2,p_1)$。
• 若 $p_2 \in [i+2, n-1]$，则会有 $(p_1,n,i+1,p_2)$。
• 若 $p_2 = n$，则会有 $(p_1,p_2,i+1,i+2)$。

于是 $p_2=i+1$。同理，会有一段连续上升的前缀被固定。贡献为 $\sum_{i=2}^{n-3} 2f_i$。

若 $p_1 = 2$，同理，$p_2 \in \{1, 3\}$。手玩一下，必形如 $(2,3,\dots,k-1,k,1,k+1,\dots,n-2,n-1,n)$ 或 $(2,3,\dots,k-1,k,1,k+1,\dots,n-2,n,n-1)$。贡献为 $2(n-1)$。

综上，将递推式化简后可得 $$ f_n = 2f_{n-1} + f_{n-3} + 2 \quad (n \ge 4) $$

执行线性递推远处求值即可。当然也可以矩阵快速幂。