考虑对于 \(a\) 建线段树，后因为每一个线段树节点管理 \(\log n\) 个 \(a_i\)，故我们可以认为有 \(n\log n\) 个关键点，那么对于每一个线段树节点建虚树。那么对于所有有关的关键点和询问点共 \(n\log n+Q\) 个点建虚树。那么我们考虑虚树上的询问点，考虑它的父亲中哪些可以成为答案。那么我们只需要考虑维护说这个点的孩子有哪些别的里面还有关键点。做两次 dfs 即可。需要用到单调栈 \(O(n)\)。那么可以在 \(O(n\log^2 n)\) 做完了。
我们希望去掉一个 $\log $，发现瓶颈在于虚树建立，瓶颈在于虚树排序。发现结构是线段树，那么我们发现先做线段树内已经排好序了，那么我们类似归并进行合并即可做到 \(O(n\log n)\)。