很妙的思路转换

显然扫描线，一个很自然的想法是用数据结构维护 $f_i$ 表示左端点为 $i$ 时…的答案，然后单点查询，但是我们发现当 $l$ 不同时，其对应的答案其实也是不好维护的

考虑这么转换，假设查询区间为 $[l,r]$ ，其内部有一个子区间 $[l’,r’]$ ，那么合法的 $l’$ 一定是 $[l,r]$ 的一段前缀，发现通过这么转化可以成功的将单点查询转化为区间查询

这样有什么好处呢？首先我们可以二分得到这个前缀的具体区间，接下来对于这个前缀内的每个 $l’$ 一定能够找到一个对应的 $r’$ 使得其合法，所以说即使对于不同的 $l$ ，只要其被包含在前缀区间内，那么他的答案都是相同的，记其为 $f_i$ ，那么我们最后要求的其实就是

$$\min_{p \in [l_e,r_e]}f_{p}-p+1$$
然后我们发现当我们对应的 $r \leftarrow r+1$ 时，我们只需要更新 $i \in [las_{a_r},r]$ 的 $f_{i}\leftarrow r$ 即可

然后就做完了