Problem Description

There are $n$ messengers on a straight line. Number them from $1$ to $n$ in order from left to right. In other words, let the coordinate of messenger $i$ be $d_i$. Then for $1 \leq i \lt n$, we have $d_i \leq d_{i + 1}$.

Messengers pass a message in the following way:

• At any moment (not necessarily an integer time), any messenger (whether they already know the message or not) may freely choose to move left, move right, or stay still. Their speed is $1$ unit length per second.
• When the distance between two messengers is no more than a given real number $k$, they can pass the message. That is, if at least one of them knows the message, then both of them will know it. Message passing happens instantly and takes no time.

Now messenger $1$ has obtained a message. Find the minimum time needed to make all messengers obtain the message.

Input Format

The first line contains a real number, the maximum distance $k$ within which message passing is possible.

The second line contains an integer, the number of messengers $n$.

Lines $3$ to $(n + 2)$ each contain a real number. The real number on line $(i + 2)$ is $d_i$, the coordinate of messenger $i$.

Output Format

This problem uses Special Judge.

Output one real number in one line, the answer. If your output differs from the standard answer by at most $10^{-3}$, you can get the score for the corresponding test point. Therefore, it is recommended that you keep at least four digits after the decimal point.

3.000 
2 
0.000 
6.000

1.500

2.000 
4 
0.000 
4.000 
4.000 
8.000

1.000

Hint

Sample 1 Explanation

In the first $1.5$ seconds, messenger $1$ walks to the right, and messenger $2$ walks to the left.

At time $1.5$ seconds, messenger $1$ is at coordinate $1.5$, and messenger $2$ is at coordinate $4.5$. The distance between them is no more than $3$, so they can pass the message.

Constraints and Notes

For all test points, it is guaranteed that:

• $1 \leq n \leq 10^5$, $0 \leq k \leq 10^6$.
• $0 \leq d_i \leq 10^9$, and for any $1 \leq i \lt n$, we have $d_i \leq d_{i + 1}$.
• In the input, each real number has exactly $3$ digits after the decimal point.

Note

This problem is translated from COCI2007-2008 COI2008 T1 GLASNICI. The translation and SPJ are provided by 一扶苏一.

Translated by ChatGPT 5