考虑固定 $k$ 求出序列 $b$。首先一定是要最小化 $b_1$，因此第一段不可能延到 $val>b_1$ 的位置，处理出 $nxt_i$ 表示下一个 $a_j>a_i$，剩余 $k>1$ 个点没放时，设当前在 $p$，若 $a_p<a_{p+1}$ 则直接跳到 $p+1$，否则后继是 $\text{argmin}(p+1\sim\min(n-k+1,nxt_p-1))$。

对于单个 $k$ 模拟依然没有很好的性质，可以对于 $k$ 从大到小扫描线，因为 $k$ 相当于限制了后继的自由程度，$k$ 越小自由程度越高，将询问离线到 $k$ 上。$k+1\to k$，从上一个决策的子序列中找到首个可以调整决策成更优的位置，由于它是因为被剩余点数限制导致第一次满足，所以后面的选取一定是后缀全连续选上。

使用数据结构维护这个子序列，处理出 $to_i$ 表示下一个 $a_j<a_i$，一个段 $(p,nxt_p)$ 的所有决策形如不断跳 $to$ 且这个过程一直在 $nxt_p$ 之前，时刻维护它的下一步决策，在对应的 $k$ 加入这个移动的决策即可。查询直接在数据结构二分即可。时间复杂度 $\mathcal O(n\log n)$。