rt，理论上 $qn\le2.5\times10^7$，$O(qn)$ 解法应该是非常宽松的，但是我自己写出来运行非常慢，不开 O2 甚至 T 了一个点（代码&评测记录），求调整/查错。

（那个非常抽象的单调队列是把 dp 值，$d_i$ 和下标按每个 $20$ 位压进一个 long long 了，我印象里这么写是比结构体快的，当然好像也有单调队列只存下标的写法，但是三次位运算的常数应该不至于在 $2.5\times10^7$ 就爆掉。）