一个很直接的思路是，维护当前可行决策集合 \(S\in\{0,\dots ,q\}\)，从 \(1\) 到 \(n\) 分别考虑每一个 \(a\)，排除一些决策，最终得到答案。
既然要排除决策，我们当然需要知道对于当前的 \(a_i\)，前 \(j\) 个操作之后的值都是多少，如果能得到这个，且这些值都在线段树上呈现，我们直接在线段树上暴力删掉值非最小值的决策，这样复杂度均摊下来就是对的，具体来说，线段树上维护区间 max 和 min 即可。我们发现如果用线段树从左到右扫的话，其实只有每个操作的差分位置会被修改，总修改次数为 \(O(q)\) 量级。
时间复杂度 \(O(q\log n)\)。