提供一个线性做法。
容斥信息应该是
$$ \begin{aligned} &\quad\; \prod_{i=1}^{n-2} ([p_i< p_{i+1}](1-[p_{i+1}< p_{i+2}])+(1-[p_i< p_{i+1}])[p_{i+1}< p_{i+2}])\\ &= \prod_{i=1}^{n-2} ([p_i< p_{i+1}]+[p_{i+1}< p_{i+2}]-2[p_i< p_{i+1}][p_{i+1}< p_{i+2}]) \end{aligned} $$
我们自然要考虑这样一个展开式如何划分出极长的 $<$ 段。注意到开头和结尾两段较为特殊，于是设 $F, G$ 表示序列中间的某一段 $[l, r]$，没有钦定 $p_{l-1}< p_l$，钦定了 $p_l< p_{l+1}<\dots< p_r$，是否钦定 $p_r< p_{r+1}$ 的关于长度的 GF；$F^\ast, G^\ast$ 表示在开头。可得方程
$$ \begin{cases} F(x) = x^2 + x F(x) + x G(x) \\ G(x) = -x^2 - 2 x F(x) - x G(x) \\ F^\ast(x) = x + x F^\ast(x) + x G^\ast(x) \\ G^\ast(x) = -2 x F^\ast(x) - x G^\ast(x) \end{cases} $$
可以解得
$$ \begin{cases} F(x) = \frac{x^2}{1+x^2} = \sum_{k\ge 1} (-1)^{k-1} x^{2k} \\ F^\ast(x) = \frac{x(1+x)}{1+x^2} = \sum_{k\ge 1} (-1)^{k-1} (x^{2k-1}+x^{2k}) \end{cases} $$
因此容斥应该就是用两个 $F^\ast(x)$ 和任意个 $F(x)$ 拼接。注意到我们可以取 $s>t$，从而可以忽略仅有一段的情况。
从而我们将所有数划分为 $[1, t-1], [t+1, s-1], [s+1, n]$，取 $a = t-1, b = s-t-1, c = n-s$，用 $x,y,z$ 分别计量三种数。
于是 $F^\ast(x)$ 会变成
$$ \sum_{k\ge 0} (-1)^k \left(\frac{x^{2k}}{(2k)!}+\frac{x^{2k+1}}{(2k+1)!}\right) = \frac12\left[(1-i)\mathrm e^{ix} + (1+i)\mathrm e^{-ix}\right] $$
和 $\frac12\left[(1-i)\mathrm e^{iz} + (1+i)\mathrm e^{-iz}\right]$。$F(x)$ 会变成
$$ \sum_{k\ge 1} (-1)^{k-1} \sum_{u+v+w=2k} \frac{x^uy^vz^w}{u!v!w!} = 1-\frac12\left[\mathrm e^{i(x+y+z)}+\mathrm e^{-i(x+y+z)}\right] $$
即需要计算
$$ \frac14\left[\frac{x^ay^bz^c}{a!b!c!}\right]\left[(1-i)\mathrm e^{ix} + (1+i)\mathrm e^{-ix}\right]\left[(1-i)\mathrm e^{iz} + (1+i)\mathrm e^{-iz}\right] \frac1{\frac12\left[\mathrm e^{i(x+y+z)}+\mathrm e^{-i(x+y+z)}\right]} $$
由于 $a+b+c=n-2$，根据载谭 Binomial Sum 的经验，我们首先要计算
$$ \begin{aligned} f(w) &= \frac1{\frac12[(1+w)+(1+w)^{-1}]} \bmod w^{n-1} \\ &= \frac{1+w}{1+w+\frac{w^2}2} \bmod w^{n-1} \\ &= -w f(w) - \frac{w^2}2 f(w) + 1 + w + \Delta_0 w^{n-1} + \Delta_1 w^n \\ &= \frac{1 + w + \Delta_0 w^{n-1} + \Delta_1 w^n}{1+w+\frac{w^2}2} \end{aligned} $$
从而我们只需要求出
$$ f(w-1) = \frac{2(w + \Delta_0 (w-1)^{n-1} + \Delta_1 (w-1)^n)}{1+w^2} $$
的各项系数。记 $u_j = [w^j] f(w-1)$，答案就是
$$ \frac14\sum_{j=0}^{n-2} u_j \left[\frac{x^ay^bz^c}{a!b!c!}\right]\left[(1-i)\mathrm e^{ix} + (1+i)\mathrm e^{-ix}\right]\left[(1-i)\mathrm e^{iz} + (1+i)\mathrm e^{-iz}\right] \mathrm e^{j\cdot i(x+y+z)} $$
另外注意到答案显然没有虚部，可以减少一些无用运算。
时间复杂度 $O(n)$。