solution complexity: O(nlog^2n)

Firstly let's notice that the maximum weight that he needs to swap is the inversion with the maximum sum in the subarray [l,r]. So let's consider that our indexes of the books that give maximum answer are ansl and ansr. Now we can see that number at index ansl is the maximum in the subarray [l,ansr-1], otherwise we could pick the maximum and get a bigger answer.

We need to make a merge-sort tree, and at each node we need to store the answer for it's subtree. So if we get a query for range [l,r] we should break that subarray to the nodes of our MS tree. Now there are two variants

1.ansl and ansr are in the same node. In this case we can just take the maximum answer for our nodes in MS tree.

2.ansl and ansr are in different nodes. For every node we should know the maximum number in nodes that are located lefter than our current node, let's call it mx. So if the ansr is located in our current node ansl will be the index of mx. We can get ansl by BS at our current node.