考虑 Q 确定了之后 P 的方案数是多少。
容易发现，P'_n=n，并且如果我们找到 n-1 的位置设为 i，假如原来的 P 中 n-1 在 n 的前面，那么 P_{i+1} 一定为 n，因为 n-1 是除了 n 之外最大的数，如果 n-1 停在了 i 这个位置，那么说明 n-1<P_{i+1}，那么 P_{i+1} 就只能为 n 了，并且 i+1 及后面的位置在 P' 确定之后只有 1 种填法。
如果 n-1 在 P 中的位置在 n 后面，设 P 中 n 的位置为 j，那么 P'_{j-1}=\max\{P_1,P_2,\dots,P_{j-1}\}，并且 j+1 及后面的位置在 P' 确定之后只有 1 种填法。
因此，我们可以归纳地证明，Q 确定之后 P 的方案数就是 2^c，c 是 Q 的前缀最大值个数减去 1。
而这个 2^c 不太好处理，我们考虑对二元组 (Q,S) 计数，S 是一个集合，表示 S 中的每个元素都是前缀最大值，但是不要求所有前缀最大值的位置都在 S 中，例如 Q=[1,2,3,4,5]，那么 S=\{1,3,4\} 是合法的。
设 f_{i,j} 表示前 i 个元素中第 i 个元素是前缀最大值，恰好为 j 符合条件的 S 数量，辅助数组 g_{i,j} 表示前 i 个元素中第 i 个元素是前缀最大值，至多为 j。边界情况为 f_{0,0}=1，答案为 f_{n,n}，容易发现 g_{i,j} = \sum_{k=1}^j f_{i,k}。
然后考虑转移，为了方便，这里只转移 Q_i=-1 的情况，首先，枚举 Q_i=k，再枚举 1 \le j \le i，满足 \max_{l=j}^i Q_l \le Q_i，然后 f_{i,k} \gets g_{j-1,k-1} \times A_{a}^b，其中 a 是 1 \sim k-1 没有确定的元素（即 1 \le Q_j \le k-1 的 j 的个数）减去 Q_1 \sim Q_{j-1} 中 -1 的个数（已经选择的），b 是 Q_j \sim Q_{i-1} 中 -1 的个数，注意，枚举 k 的时候要确保没有 Q_j=k。
上面转移的组合意义很简单，就是把 a 个数按照顺序填入 b 个空的方案，就是 A_a^b = \frac{a!}{(a-b)!}。
最后把 A 的两个阶乘拆开，就可以直接分离贡献，用前缀和优化到 O(n^2) 了，怎么分离就不细讲了，留作读者思考。
时间和空间复杂度都是 O(n^2)。