这是一个“分步”进行构造的过程，每一步关联不大。所以我们先研究每一步有什么性质。

假设你现在有长度为 $n$ 的序列，你需要在第 $i$ 个元素之后插入一个 $x$，字典序变大当且仅当？

你考查你插入后的序列，找到那个你插入的元素。其后面第一个第一个与前一个数字不同的数字比他前面的数字大，或者其后面的所有数字相等。

好吧我错了。

考虑加元素是困难的，考虑删元素。

然后你发现对于一个连续段来讲你删任意一个都是等价的，所以我们钦定每次删最右边那个。

这相当于每次删 $a_i > a_{i+1}$ 的地方。这看起来容易多了。

我错了，我好菜。

我们设 $f_{i,j}$ 为考虑长度为 $i$，值域为 $k$ 的。

我一直在试图一个一个加，结果发现还是做不了。

主要是你发现这个东西你还是要知道全局信息。

题解说：我们分治！

然后你直接枚举 $1$ 的出现位置和出现时间，然后分成前后两半。

做完了。

为什么我这么蠢啊。