MO's Sorting Order

Sort queries by:

$1.$ Primary: block of left endpoint ($\lfloor l/B \rfloor$)

$2.$ Secondary: right endpoint ($r$) Within the same block of $l$, right endpoints are sorted. So $r$ only increases (or decreases after a block change), limiting movement. Across all queries in one $l$-block, $r$ moves at most $n$ positions total. There are $\sqrt{n}$ blocks, so total $r$ movement is $O(n\sqrt{n})$. The $l$ pointer moves at most $B = \sqrt{n}$ within a block, and there are $q$ queries, so total $l$ movement is $O(q\sqrt{n})$. Combined: $O((n + q)\sqrt{n})$.