以下是我补这道题时的经历：

我按照官方题解的流程，使用 ST 表维护。

一开始我没有仔细想，就粗略地把答案上界设为了 $n^2$。

虽然时间复杂度同样是 $O((n+q)\log^2{n})$ 的，但我的代码由于时限是 1.5s 而被卡常了——在 #9 TLE 了。（官方题解是相同的复杂度，但它用的似乎是树状数组）

我把答案上界改为了 $n$，结果 #9 就在 1s 内过了，但 #19 又 WA 了。

通过观察 #19 数据点，我决定把上界改为 $4n$，结果就过了——用时接近 1.4s。

所以有人能证明一下答案 $\le 4n$ 吗？或者干脆证伪然后把我 Hack 掉？

再或者可以帮我卡卡常？

AC 提交记录：https://codeforces.com/contest/1707/submission/164578051