Dynamic Social Distancing

There are \(N\) people standing on a number line with initial positions \(a_1,a_2,\ldots,a_N\). Each of them can move at a speed of 1 unit per second. Due to safety guidelines, any two people must maintain a distance of at least \(D\) from each other.

Alenka designed an app to quickly calculate the minimum time required for these people to reposition themselves so that the social distancing requirement holds. The relocation strategy is as follows: sort the positions and assign new positions in an arithmetic progression \(x, x+D, x+2D, \ldots\) such that the maximum movement needed by any person, \(T\), is minimized. In other words, if after sorting the positions we denote them as \(x_0,x_1,\ldots,x_{n-1}\), we need to choose \(x\) minimizing

\(T = \max_{0\le i < n} \left| x_i - \Bigl( x + i\cdot D \Bigr) \right|\).

It can be shown that the optimal \(x\) is the median of \(\{ x_i - i\cdot D : 0 \le i < n \}\). Now, the app is extended to support dynamic updates: after the initial configuration, additional persons at given positions \(b_i\) are added one by one. After each addition, you need to recompute and output the new minimum time required.

inputFormat

The first line contains two integers \(N\) and \(D\) representing the initial number of people and the required minimum distance.

The second line contains \(N\) space-separated integers \(a_1, a_2, \ldots, a_N\) denoting their positions.

The third line contains an integer \(Q\) representing the number of queries (new persons to add).

Each of the next \(Q\) lines contains an integer \(b_i\) indicating the position of the new person.

outputFormat

Output \(Q+1\) lines. The first line is the minimum time required for the initial configuration. Each of the next \(Q\) lines corresponds to the new minimum time after adding a person. Answers may be non‐integer values and should be printed with at least 6 decimal places.

sample

3 2
1 3 6
2
4
10

1.000000
0.500000
1.000000