考虑从小到大加数。加数时记录位置最前的两个递增的位置 $p$ （也就是第一次出现非完全倒序的地方），当加入当前数 $i$ 时，若 $i$ 插在 $p$ 的后面，则会形成满足条件的三元组，所以 $i$ 只能插在 $1-p$ 的任意一个位置中，若插在位置 $1$ 中，则 $dp[p]$ 转移到 $dp[p+1]$ ，若插在 $2-p$ 中的其中一个位置 $q \le p$ 则由 $dp[p]$ 转移到 $dp[q]$ 。

然后对于没有限制数的即可得到一个 $O(n^3)$ 的dp，发现转移是一个后缀区间，即可使用后缀和优化变为 $O(n^2)$。

现在考虑有限制数的情况，当加入 $x$ 时，在原来的 $dp$ 上加上一维 $dp[posx][p]$ ，插入时讨论一下 $posx$ 是否需要后移一位，按照原方法做 $dp$ 即可，时间复杂度为 $O(n^3)$。