Message Propagation on a Line

There are \(n\) messengers located on a one-dimensional line, with messenger \(i\) positioned at \(d_i\). The coordinates are given in non-decreasing order, i.e. \(d_1 \le d_2 \le \cdots \le d_n\). Initially, only messenger 1 has a message.

Every messenger may move at any time (the time need not be an integer) with a constant speed of \(1\) unit per second. They can independently choose to move left, right, or stay still. Importantly, regardless of whether a messenger has already received the message, they can freely move according to a pre-arranged plan.

At any moment, if two messengers are within a distance of \(k\) (a given real number), they can instantly exchange the message (i.e. if one has the message, then both will have it immediately). The goal is to determine the minimum time required so that, following an optimal movement strategy, all messengers receive the message.

Hint: An effective strategy is to plan a chain of meetings along the line. Even though the message starts at messenger 1, all messengers (even those who have not yet received the message) can begin moving from time \(0\) according to a coordinated plan. When two adjacent messengers with initial positions \(d_i\) and \(d_{i+1}\) meet, they only need to get within a distance \(k\) of each other. Since both can move at speed 1, this meeting can be arranged in at least \(\max\Big(0, \frac{d_{i+1} - d_i - k}{2}\Big)\) seconds. However, because the meeting events must form a chain (i.e. the messenger who meets the previous one must then later meet the next messenger), the overall minimal time is determined by an optimal combination of these movements.

A neat solution is to simulate the chain propagation from left to right. Define a variable \(M\) representing the effective (rightward) meeting position of the messenger that most recently received the message. Initially, \(M = d_1\) and the time is \(0\). Then, for each messenger \(i\) from \(2\) to \(n\), compute:

[ \text{gap} = d_i - M - k, ]

if \(\text{gap} > 0\) then an extra time of \(t = \frac{\text{gap}}{2}\) seconds is required to close the gap, and update \(M = d_i - t\); otherwise, set \(M = d_i\) (no extra time is needed because messenger \(i\) is already close enough).

The answer is the sum of all extra times.

inputFormat

The first line contains two numbers: an integer \(n\) (\(1 \le n \le 10^5\)) and a real number \(k\) (\(k \ge 0\)). The second line contains \(n\) space-separated numbers \(d_1, d_2, \ldots, d_n\) (\(0 \le d_i \le 10^9\)) representing the coordinates of the messengers, given in non-decreasing order (i.e. \(d_i \le d_{i+1}\)).

outputFormat

Output a single real number: the minimum time (in seconds) required so that all messengers receive the message. The answer is accepted if its absolute or relative error does not exceed \(10^{-6}\).

sample

2 4
0 10

3.000000