条件 $1$ 等价于：出现过的值构成一段值的前缀 $[0,k]$，并且考虑每种值的首个出现位置，一定随 $0\to k$ 是递增的。

条件 $2$ 的入手点分为从固定 3 和固定 2，经过一些尝试，固定 2 的角度似乎只有一些 $\mathcal O(n^4)\sim \mathcal O(n^5)$ 的做法。

思路就是按照值的顺序来填写，如果是从小到大，那么要记录的值信息是比较多的。换一个角度，直接确定好最终的 $k$，然后从大到小统一插入新的同一种值。考虑插入一个值作为 3 的情况，更小的值在之后一定是一个递降的子串。所以我们不妨做一个延迟钦定，先在这里确定好它是较小值的位置，再在后面确定具体的取值。

状态即为 $f_{i,x,y}$ 表示考虑了值 $\ge i$ 的数，它们一共使用了 $x$ 个位置，然后下传了 $y$ 的空位。转移首先要把 $y$ 转移到所有 $y'\leq y$ 的位置上，表示上面这些空位，将一段前缀转化成值 $v$。然后考虑逐个往前添加数，也就是说满足条件 $1$：第一个值为 $v$ 的位置以及第一个值为 $v+1$ 的位置中会添加一些数。按照 $x$ 的顺序转移，每次决策向前加的数它是 $v$ 还是 $\leq v-1$ 的数，这里逐个决策是要比一个状态直接枚举个数向后贡献更优的，类似于一个完全背包的优化。

对于一个 $k$ 就做到了 $\mathcal O(n^3)$，对于不同的 $k$，有两种优化方向：交换 dp 的起终点，转置原理优化；对于 $f$ 记录所有 $k\ge i$ 的总和，并不需要区分哪个 $k$，每次做完 $v$ 后加入 $k=v$ 的贡献。

总复杂度 $\mathcal O(n^3)$。