Prepared by: Ivan Paljak, Paula Vidas, and Dominik Fistrić

Consider the situation when there are ~N~ people standing at coordinates ~a_1, \dots, a_N~, and without loss of generality let the coordinates be sorted, i.e. ~a_1 \le \dots \le a_N~.

It's easy to see that there exists an optimal rearrangement after which the order of the people remains the same as the initial order. Otherwise, if there is a moment when some two people swap places in the order, the total time won't increase if they instead don't change their relative order at that moment (but instead move where the other person would have moved).

Let ~t_{i,j} = \frac 1 2 ((j-i)D-(a_j-a_i))~, for any ~i \le j~, and let ~t = \max_{i \le j} t_{i,j}~. We claim that ~t_{opt}~ is equal to ~t~.

Clearly, ~t~ is a lower bound. After ~t'~ seconds, the distance between people ~i~ and ~j~ can be at most their initial distance ~a_j-a_i~ plus ~2t'~. Thus ~a_j-a_i+2t_{opt} \ge (j-i)D~, which implies ~t_{opt} \ge \frac 1 2 ((j-i)D-(a_j-a_i)) = t_{i,j}~.

Now we prove ~t~ is an upper bound. Consider the following greedy strategy. Let ~b_1, \dots, b_N~ be the final coordinates, calculated as: ~b_1 = a_1-t~, and ~b_i = \max(a_i-t, b_{i-1}+D)~ for ~i > 1~. First, we prove that nobody moved more than ~t~. For some person ~j~, let ~i \le j~ be the maximal index such that ~b_i = a_i-t~. Then, we can see that ~b_j = b_i+(j-i)D~, so ~b_j-a_j = (j-i)D+b_i-a_j = (j-i)D+a_i-t-a_j \le 0~. On the other hand, ~b_j \ge a_j-t~, i.e. ~b_j-a_j \ge -t~, so we're done. Second, we prove that after the rearrangement, no two consecutive people are standing closer than ~D~. This follows from ~b_i \ge b_{i-1}+D~, and the proof is complete.

Naively calculating all ~t_{i,j}~ and taking the maximum one, for each of the ~M~ scenarios, is enough to solve the first subtask. Time complexity is ~\mathcal O(M(N+M)^2)~.

To solve the second subtask, we don't need the formula. Instead, we can binary search ~t_{opt}~ directly. To check if some ~t'~ is feasible, we use the greedy strategy from the proof above, and at the end check if all consecutive distances are at least ~D~. Time complexity is ~\mathcal O(M(N+M) \log T)~, where ~T~ is the maximum possible value of ~t_{opt}~ given the constraints.

The third subtask can be solved using the formula for ~t~. We can rewrite ~t_{i,j} = \frac 1 2 ((a_i-iD)-(a_j-jD))~. Since each new person is added to the end of the line, it's enough to maintain the current maximum value of ~a_i-iD~. Then, when ~j^\text{th}~ person is added, it's easy to find the maximal ~t_{i,j}~ over all ~i~. Time complexity is ~\mathcal O(N+M)~.

In order to solve the fourth subtask, we need to be able to insert a person at an arbitrary place in the line. Consider the value ~a_i-iD~. When a person is inserted somewhere in the middle of the line, this value remains the same for everyone on the left side, and decreases by ~D~ for everyone on the right side of this person. Furthermore, values ~t_{i,j}~ remain the same between people who are on the same sides relative to the new person, and it increases by ~D~ between people on opposite sides. Therefore, to find the new ~t_{opt}~, it's enough to find the maximum of ~a_i-iD~ in the left part and the minimum in the right part.

This process can be simulated using a segment tree which supports adding a number to a range and querying for minimum and maximum of a range. This is a classic problem, for more info check this link. Time complexity is ~\mathcal O((N+M) \log(N+M))~.