首先扔出一个结论，如果 Q 中没有 -1，那么答案是 2^k，其中 k=\sum_{i=2}^n [Q_i=\max(Q_{1\sim i})]。考虑证明。
设 Q_i=\max(Q_{1\sim i}) 的位置（包含 i=1）是 a_1\sim a_{k+1}。那么设 f_i 为 1\sim a_i 的答案，显然 f_1=1。考虑 Q_{a_i} 放哪。我们发现可以插在前面一个前缀最大值 a_j 的正后方，而 a_j+1\sim a_i 是啥都固定了，并且 1\sim a_j 是 f_j。还有一种情况是插在最前面。那么得出 f_i=\sum_{j=1}^{i-1}f_j+1，则 f_1=1,f_2=2,f_3=1+2+1=4,f_4=1+2+4+1=8,\cdots, f_{k+1}=2^{k}。
因此设 f_{i,j} 为前 i 位，现在 \max 是 j 的答案即可。为了方便，设 Q_0=0，最后答案是 \frac{f_{n,n}}{2}。