Analysis
（一）
猜想：答案跟 $q_1, q_2, q_3$ 无关；考虑排列 $q$ 是 $1, 2, 3$ 的情况，此时符合要求的排列 $p$ 实际上满足：
对于任意 $i < j < k$ 有 $p_i, p_j, p_k$ 不是单调递增的。
（二）
注意到：$1$ 到 $n-1$ 的排列仍需满足上述条件，而 $1$ 到 $n$ 的排列是由向 $1$ 到 $n-1$ 的排列中的某个位置插入 $n$ 得到的，也就是说「符合要求的排列具有子结构」。考虑把 $n$ 插入到哪个位置才能不破坏上述性质，不难看出只要满足「 $n$ 之前的排列是单调递减的」即可。
因此，我们可以按「单调递减的最长前缀的长度」将所有长为 $n$ 的排列分类。
于是可令 $a[n][l]$ 表示长为 $n$ 且「单调递减的最长前缀的长度」为 $l$ 且符合条件的排列的个数。
转移方程为
egin{aligned}
a[n][l] &= mathtip{a[n-1][l-1]}{ ext{put $n$ at the beginning}} + mathtip{sum_{i = l}^{n-1} a[n-1][i]}{ ext{put $n$ after the $l$-th number}} \
&= sum_{i= l-1}^{n-1} a[n-1][i] \
&= a[n][l+1] + a[n-1][l-1]
end{aligned}
注意到数组 $a$ 的第一维可以优化掉。
时间复杂度 $O(n^2)$
空间复杂度 $O(n)$