World T20 X Team (full version)

This is the real deal: for the actual World T20 tournament, Zayan must answer many queries, each asking for a team of size X that maximizes the total pairwise rating gap, and needs every query answered instantly. Given N player ratings, answer Q queries. Each query gives X (team size). For that X, choose X players to MAXIMIZE the sum of |rating_i - rating_j| over all pairs in the chosen team. Print the answer for each query. Precompute using sorted prefix sums so each query answers in O(1) or O(log N).

5
1 2 3 4 5
2
2
4

4
10