条件等价于 $a$ 中出现过的数在 $p$ 中是一个上升子序列，于是我们只需要对每个 $k$ 求 $p$ 中有多少个长度为 $k$ 的上升子序列，记为 $f_k$。$f_k$ 可以在 $O(n^2\log n)$ 的时间里求出（按 $k$ 从小到大递推，转移用树状数组优化）。

答案即为 $\sum_{k=1}^n f_k\genfrac\{\}{0pt}{}{n}{k}k!$。时间复杂度 $O(n^2\log n)$。