일직선의 거리 위에 N개의 기지국이 있다. 두 기지국 사이의 거리가 K 이하여야 서로 통신을 할 수 있다.

허나, 지금 상태로는 모든 기지국이 서로 통신을 할 수 없는 상태이다. 따라서 방송국에서 일꾼들을 고용하여 기지국을 옮기려고 한다. 기지국을 옮기는 데 비용이 많이 들기 때문에, 최대한 적은 거리로 옮기려고 한다. 기지국의 위치가 주어질 때, 기지국을 옮기는 거리의 최댓값의 최솟값을 구하는 프로그램을 작성하여라.

입력

• 첫 번째 줄에 통신 가청 거리 K가 실수로 주어진다. (0 ≤ K ≤ 10^6)
• 두 번째 줄에 기지국의 수 N이 주어진다. (1 ≤ N ≤ 100,000)
• 세 번째 줄에서부터 N개의 줄에는 각 기지국의 좌표가 오름차순으로 주어진다. 좌표는 0 이상 10^9 이하의 실수이다.

출력

입출력 예

입력

3.000
2
0.000
6.000

출력 

1.500

입력 

2.000
4
0.000
4.000
4.000
8.000

출력

1.000

입력 예 2 설명
각 기지국을 1.000, 3.000, 5.000, 7.000의 좌표로 옮기면 최적이다.

출처:2007-2008/coci/
번역:functionx