First, let us find the size of good sets. It can be found by a greedy algorithm that sweeps points in the increasing order of coordinates and adds points if it is possible. This greedy algorithm can be optimized by binary lifting, resulting in \(O(\log N)\) time per query.

Let \(m\) be the size of good sets.

Suppose \(a_1 < a_2 <\cdots <a_m\) are the indices of points picked by the aforementioned greedy algorithm. Also, suppose that we performed the greedy algorithm in the decreasing order and that \(b_1 < b_2 <\cdots <b_m\) are the indices of points picked then.

Here, \(a_1 \leq b_1 < a_2 \leq b_2 < \cdots < a_m \leq b_m\) holds. That is because if \(a_{i+1} \leq b_i\) holded for some \(i\), we would be able to pick \(m+1\) points including \(a_{i+1}\), which contradicts maximality of \(m\).

The size of the union of good sets is \(\sum_{i=1}^m (b_i-a_i+1)\). This is shown as follows. First, consider a point \(p\) which satisfies \(a_i \leq p \leq b_i\) for some \(i\). Picking appropriate points in the left and the right of \(p\), we have a good set that contains \(p\). Conversely, if \(p\) does not satisfy the precondition described above, then \(p\) necessarily satisfies \(b_i < p < a_{i+1}\) for some \(i\). For such \(p\), we can pick at most \(i-1\) points in \(p\)’s left and \(m - i - 1\) points in \(p\)’s right, which implies we can pick at most \(m-1\) points. Therefore, \(p\) cannot be a member of a good set.

After all, we want the sum of indices obtained by the greedy algorithm from left to right, and its right-to-left counterpart. They can be calculated efficiently by using binary lifting. The overall time complexity is \(O(N\log N+Q\log N)\).