まず，よい集合のサイズを求めてみます． これは座標の小さい点から順に見ていって，点を追加できるなら追加するという貪欲法で解けます． そして，この貪欲法はダブリングによって高速化でき，クエリあたり \(O(\log N)\) の計算量になります．

今，よい集合のサイズが \(m\) だとします． 上記の貪欲法によって選ぶ点の番号が，\(a_1 < a_2 <\ldots <a_m\) だとします． また，上記の貪欲法を，座標の大きい点からも行ったとします． この貪欲法によって選ぶ点の番号が，\(b_1 < b_2 <\ldots <b_m\) だとします．

ここでまず，\(a_1 \leq b_1 < a_2 \leq b_2 < \ldots < a_m \leq b_m\) であることがわかります． もしある \(i\) に対して \(a_{i+1} \leq b_i\) であったとすると，点 \(a_{i+1}\) を含む \(m+1\) 個の点を同時に選ぶことができ，\(m\) の最大性に反します．

このとき，よい集合の和集合のサイズは \(\sum_{i=1}^m b_i-a_i+1\) になります． これは，次のようにわかります． まず，ある \(i\) に対して \(a_i \leq p \leq b_i\) を満たす点 \(p\) について考えると，\(p\) の左と右で適切な点を選ぶことで，点 \(p\) を良い集合に含めることができます． 逆に，上記の条件を満たさない点，つまり \(b_i < p < a_{i+1}\) を満たすような点 \(p\) については，\(p\) の左で選べる点の個数が最大 \(i-1\) 個，右で選べる点の個数が \(m-i-1\) なので，合計 \(m-1\) 個しか選べないことになり，よい集合に含まれません．

結局，左から貪欲を行ったときに取る点集合の index の総和，及び右から貪欲を行ったときに取る点集合の index の総和が求まれば，各クエリの答えは求まります． そしてこれはダブリングを用いて計算することが可能です． 計算量は全体で，\(O(N\log N+Q\log N)\) となります．