设 \{p_i\} 的 LIS 长度为 K。
容易发现，a_i\in\{K-1,K\}。
下文默认固定 K，将 a_i 都减去 K。
划分
将排列中每个数划分为四种类型：
- 绿色点：LIS 上不可替代的点。
- 红色点：LIS 上可替代的点。
- 黑色点：用来替代红色点的点。
- 蓝色点：无用点。
如：
{\color{red}3},\,{\color{black}2},\,{\color{blue}1},\,{\color{green}4},\,{\color{red}6},\,{\color{black}5}
如果一个红色点有多个可以用于替代的黑色点，只需保留最靠前的即可，其他视为蓝色点。
同理，可以证明，对于每个红黑点对，选择位置靠前的作为红点，替换黑点时一定不会发生需要替换其他点的情况。
一种错误的染色方法：
{\color{black}3},\,{\color{red}1},\,{\color{red}4},\,{\color{black}2}
需要用 \color{black}3 替换 \color{red}1 时，必须用 \color{red}4 替换 \color{black}2。
观察
考虑两个答案不同，当且仅当 K 不同或每个位置 0、-1 的取值不同。
以下是四种点对应的情况：
- 绿色点：K 增加 1，此处为 -1。
- 红色点：K 增加 1，此处为 0。
- 黑色点：K 不增加，此处为 0。
- 蓝色点：K 不增加，此处为 0。
可以发现，黑色点和蓝色点对答案的影响完全一致。
之所以黑色点会存在，是因为红色点需要一个「匹配」。
换言之，黑色点只会紧贴着红色点出现。
计数
对于确定的 K 以及满足题意的序列 \{a_i\}，考虑将其对应到唯一一种染色方案上。
- 对于 -1，只能放绿。
- 否则，由于 K 已经确定，红黑对的数量也已经确定。
- 贪心地让红黑对尽量排在前面。
- 需要注意的是，可能出现 {\color{red}3},\,{\color{black}2},\,{\color{blue}1},\,{\color{green}4},\,{\color{red}6},\,{\color{black}5} 的情况。
- 如果仅剩一个空位（再下一个是绿点），就只能放蓝了。
建出自动机：
$1$：最后放了一个红，下一个必须放黑。
$2$：最后放了一个蓝，下一个只能放绿或蓝，如果再放一个蓝的就不能放红黑对了。
$3$：红黑对放完了，下一个只能放绿或蓝。
考虑转移：
$$
\begin{aligned}
f'_{0,K+1} &\gets f_{0,K} & {\color{green}\text{绿}} \\
f'_{1,K+1} &\gets f_{0,K} & {\color{red}\text{红}} \\
f'_{2,K} &\gets f_{0,K} & {\color{blue}\text{蓝}} \\
f'_{0,K} &\gets f_{1,K} & {\color{black}\text{黑}} \\
f'_{0,K+1} &\gets f_{2,K} & {\color{green}\text{绿}} \\
f'_{3,K} &\gets f_{2,K} & {\color{blue}\text{蓝}} \\
f'_{3,K+1} &\gets f_{3,K} & {\color{green}\text{绿}} \\
f'_{3,K} &\gets f_{3,K} & {\color{blue}\text{蓝}}
\end{aligned}
$$
时间复杂度 $\mathcal{O}(nm)$。
[提交记录](https://atcoder.jp/contests/agc055/submissions/38935975)。