这启发我们将序列分块．设块长为 B，则第 i 个块左端点为 (i-1)B+1，右端点为 iB．若 (i-1)B < j < i B，则一定有 f_{(i-1)B+1} \le f_j \le f_{i B}．以当前块和下一块的左端点的 f 值求出当前块中其他位置的 f 值，进而求出最终答案．
考虑如何求 f，常见的方法是单调队列，但本题由于具有全局空间限制而无法使用．另一种方式是采用数据结构维护区间最小值和最小值下标，由于本题对全局空间的限制，使用分块维护是一个比较好的选择．我们在第一次遍历 a 数组的时候维护目前扫过的所有整块和右散块的最小值和最小值下标，则可以在扫描至 ((i-1)B+1) + k - 1 时求出 f_{(i-1)B+1}．
在第二次遍历时，我们需要对块中的非左端点元素求出 f_i．我们逐块考虑，设目前处理的是第 i 块．若不考虑全局空间限制，存在一个使用双端单调队列的方法：维护一个类型为（下标，值）二元组，且按照值从左到右严格递增的双端单调队列．遍历 a 的 [f_{(i-1)B+1}, f_{iB}] 子区间．遍历到下标 p 时将 (p,a_p) 加入队列右端．加入下标为 p 的元素前将队列左侧所有下标小于 p-k+1 的元素删除．加入下标为 p 的元素后，如果下标 p-k+1 是当前块的非左端点，则以双端单调队列最左侧元素的值汇报 p-k+1 处的答案．如果加入 f_{iB} 后仍然有块内位置没有被汇报答案，则以双端单调队列最左侧元素的值汇报剩余位置的答案．
接下来考虑全局空间限制．观察到如果我们给双端队列设置一个最大长度 L，在即将在右端加入元素时，若当前队列元素个数已经为 L，则不加入．当取 L=B+O(1) 时，不会影响最终的答案．对此有一个简单的证明：我们将 [f_{(i-1)B+1}, f_{iB}] 的下标按照 \leq iB + k - 1 和 > iB + k - 1 分为两部分．第一部分最多包含 B 个下标，这些下标一定能成功加入双端队列，故如果答案来自这一部分则不会受到影响．对于第二部分，属于这一部分的下标一旦被加入双端队列就不可能从左侧弹出，只能从右侧弹出，也就是说若这一部分中的一个下标 p 成为了某个位置的 f 值，则在 p 对应的元素加入双端队列前，一定会先 pop 掉所有下标 > iB + k - 1 的元素，此时双端队列内的元素个数一定 \leq B，故 p 一定能成功加入双端队列．
这个做法的时间复杂度为 O(n + (\frac{n}{B})^2)，空间复杂度为 O(B + \frac n B)．当 B = O(\sqrt n) 时，时间复杂度为 O(n)，空间复杂度为 O(\sqrt n)．可以通过本题．