Bánh rất thích chơi Game, ba bảo lớn lên con chỉ có hai con đường, hoặc rất giàu hoặc giữ xe quán Net. Bánh nói con sẽ rất giàu vì con sẽ lập trình Game. Một game mà ý tưởng của Bánh đề xuất như sau: Cho một dãy các quả mìn đặt trên một đường thẳng trên màn hình ở các vị trí nguyên ~x_1, x_2, \ldots, x_n~. Một tác động lên một vị trí thuộc đường thẳng chứa các quả mìn trên với một năng lượng ~R~ (ví dụ thời gian touch) sẽ làm cho các quả mìn thuộc đoạn ~x - R,\ldots, x + R~ nổ tung và kéo theo phản ứng dây chuyền từ các vị trí của các quả mìn bị nổ sẽ kích thích các quả mìn khác cùng phạm vi như trên nhưng ~R~ giảm đi ~1~ đơn vị cùng nổ, hiệu ứng đó kéo dài cho đến khi ~R = 0~.

Hãy lập trình cho ý tưởng của Bánh bằng cách tìm năng lượng ~R~ nhỏ nhất sao cho tất cả các quả mìn trên đường thẳng đều bị nổ.

Input

Dòng đầu tiên chứa số nguyên ~n~ thỏa ~2 \le n \le 50000~.

~n~ dòng kế tiếp, mỗi dòng chứa một số nguyên ~x_i~ thỏa ~0 \le x_i \le 10^9~.

Output

In ra ~R~ làm tròn đến ~1~ chữ số sau dấu chấm thập phân.

Samples

Sample Input 1

5
8
10
3
11
1

Sample Output 1

3.0

Note

Tác động với năng lượng ~R = 3.0~ tại vị trí ~5~, các quả mìn trong phạm vi là ~3, 5, 8~ sẽ nổ, kéo theo hai quả mìn là ~1~ và ~10~ sẽ nổ với ~R = 2~ tính từ ~3~ và ~8~, kéo theo quả ~11~ sẽ nổ với ~R = 1~ tính từ vị trí ~11~. Tất cả các quả đều nổ. Game over!!!