自想题求原/更优解

给定 $s<a_i<t(1\le i\le n)$，初始序列为 $[s,t]$，要将所有的 $a_i$ 按排列 $p$ 的顺序插入。满足：

目前只能想到 $O(n^3)$ 的暴力区间dp，望找有没有类似原题/小于等于 $O(n^2)$ 做法。