整体二分做法假了，悲伤。

放了一堵墙之后后面的数怎么填。设 最大为 ，不妨假设询问的 ，那么 一定有贡献。其它的点可以按降序排在 的后面，这样就只有 有贡献。这么做的问题在于，我们可以在 和 中再插入一些点，使得每个点的贡献都比原来 一个点的贡献大。

我们不妨决策在 的左边放哪些点，显然这是个递增序列（如果不递增，可以把那个下降的位置放到 后面，这个点就没贡献）。所以将所有询问和原序列元素放在一起按照 降序排序。设 表示递增序列的第一个元素为 的答案 (状态中记录第一个元素，这样回答询问时调用对应的 DP 值即可)。那么有 。

设 。显然，对于两个数 ， 和 之间只有至多一个交点，即存在一个“赶超时刻”，使得在此之前 更优，在此之后 更优。那么我们可以用单调栈维护所有的决策点，栈中的元素满足下标递增，相邻元素的交点也递增。

考虑有上界之后怎么办，容易发现如果 ，那么 ，那么 ，也就是说，如果存在 ，使得 ，那么可以推出 ，而因为 ，