#3009. 消息传递

消息传递

Description

有N个人在一直线上,第i个人的位置为Di,满足Di≤Di+1。最初只有第1个人(在最左边)知道消息。

在任意时刻,每个人可以以每秒1单位的速度向左或向右移动,或者停在原地。如果两个人的距离不超过K,那么就可以进行消息传递。求所有人都知道消息最少需要多少时间。

Format

Input

第一行一个正实数K,表示最大的消息传递距离;

第二行一个整数N,表示有N个人;

以下N行,每行一个正实数,表示每个人的位置,第i行表示第i个人的位置Di

Output

输出共一行一个实数,即所有人知道消息的最短时间。(结果保留三位小数点,四舍五入)

Samples

3.000
2
0.000
6.000
1.500

Tips

对于30%的数据:1≤N≤2,000;

对于100%的数据:0≤K≤10^6;1≤N≤10^5;0≤Di≤10^9;