문제
일직선의 거리 위에 N개의 기지국이 있다. 두 기지국 사이의 거리가 K 이하여야 서로 통신을 할 수 있다.
허나, 지금 상태로는 모든 기지국이 서로 통신을 할 수 없는 상태이다. 따라서 방송국에서 일꾼들을 고용하여 기지국을 옮기려고 한다. 기지국을 옮기는 데 비용이 많이 들기 때문에, 최대한 적은 거리로 옮기려고 한다. 기지국의 위치가 주어질 때, 기지국을 옮기는 거리의 최댓값의 최솟값을 구하는 프로그램을 작성하여라.
입력
첫 번째 줄에 통신 가청 거리 K가 소수점이하 3자릿수의 실수로 주어진다. (0 ≤ K ≤ 106)
두 번째 줄에 기지국의 수 N이 주어진다. (1 ≤ N ≤ 100,000)
세 번째 줄에서부터 N개의 줄에는 각 기지국의 좌표가 오름차순으로 주어진다. 좌표는 0 이상 109 이하의 실수이다.
출력
기지국을 옮기는 거리의 최댓값의 최솟값을 출력한다. 정답과의 차이가 0.001 이하이면 전부 정답 처리한다.
예제1
입력
3.000
2
0.000
6.000
출력
1.500
예제2
입력
2.000
4
0.000
4.000
4.000
8.000
출력
1.000
힌트
출처
COCI 2007/2008