Messengers

A straight road connects two villages. Along the road stand N messengers. The first messenger, the one closest to the first village, initially knows a piece of news. The messengers want everyone to learn it as quickly as possible.

The process follows these rules:

• Every messenger may start moving at any time, in either direction, with speed at most 1 unit per second. A messenger may also stand still.
• Every messenger who knows the news shouts it continuously.
• A messenger hears the news as soon as the distance to any shouting messenger is at most K units.

Given the initial positions of the messengers, determine the minimum number of seconds required until all messengers know the news. Positions are measured as distances from the first village. Initially, only the first messenger knows the news.

The first line contains a real number K (0 <= K <= 10^6), the maximum distance at which one messenger can hear another.

The second line contains an integer N (1 <= N <= 100000), the number of messengers.

Each of the next N lines contains one real number D (0 <= D <= 10^9), the distance of a messenger from the first village. The distances are given in nondecreasing order. Several messengers may start at the same position.

Print one real number: the minimum time, in seconds, until all messengers know the news.

Your answer is accepted if its absolute or relative error is at most 0.001.