Bessie는 완전히 독창적이고 대히트할 거라 믿는 “화난 소” 게임을 만들었습니다. 플레이어는 새총으로 소를 일차원 수직선 곳곳의 건초 더미로 쏩니다. 착지 힘이 가까운 더미를 터뜨리고 연쇄 반응으로 더 터질 수 있습니다. 한 소로 모두 터뜨리는 것이 목표입니다.

$N$개 더미가 서로 다른 정수 위치 $x_1, x_2, \ldots, x_N$에 있습니다. 위력 $R$인 소가 $x$에 착지하면 “반지름 $R$” 폭발이 $x-R \ldots x+R$의 더미를 덮습니다. 이들은 모두 동시에 반지름 $R-1$로 터집니다. 폭발에 덮인 아직 안 터진 더미는 모두 동시에 반지름 $R-2$로 터지며 계속됩니다.

한 소가 적절한 위치에 착지하여 최종적으로 모든 더미를 터뜨릴 최소 위력 $R$을 구하세요.

입력

첫 줄은 $N$($2 \leq N \leq 50,000$), 나머지 $N$개 줄은 정수 $x_1 \ldots x_N$으로 각각 $0 \ldots 1,000,000,000$입니다.

출력

최소 위력 $R$을 반올림하여 소수점 아래 정확히 1자리로 출력하세요.

예제

입력 1

5
8
10
3
11
1

출력 1

3.0

참고

예제에서 위력 3으로 위치 5에 착지하면 3과 8이 즉시 터집니다. 동시에 반지름 2로 터져 1과 10을 덮고, 이들이 동시에 반지름 1로 터져 마지막 11을 덮고 그것은 반지름 0으로 터집니다.

문제 작성자: Brian Dean