依次加入 $b$ 中每个元素，维护最大的 $t$ 使得 $(a_{1\dots t},b)$ 为好的二元组。

当前往 $b$ 末尾加入一个 $x$，那么 $t$ 的变化方式为：

• 如果 $x\ge a_t$，设 $t_1$ 为 $t$ 后面第一个 $>x$ 的位置，则令 $t\leftarrow t_1-1$。

• 如果 $x<a_t$，设 $t_1$ 为 $t$ 前面第一个 $\le x$ 的位置，则令 $t\leftarrow t_1$。

预处理每个点往前第一个比它小的以及往后第一个比他大的位置，连成两棵树。在这个结构上 dp 即可做到 $O(n^2)$。