Bessie thiết kế “Bò giận dữ”, tin sẽ thành trò chơi ăn khách và hoàn toàn độc đáo. Người chơi dùng ná bắn bò vào cảnh một chiều với kiện cỏ trên trục số. Lực đáp làm nổ kiện gần, có thể gây phản ứng dây chuyền. Mục tiêu dùng một bò làm nổ tất cả.

$N$ kiện ở vị trí nguyên khác nhau $x_1, x_2, \ldots, x_N$. Bò với sức mạnh $R$ đáp ở $x$ gây nổ “bán kính $R$”, phủ $x-R \ldots x+R$. Tất cả kiện ấy nổ đồng thời với bán kính $R-1$. Kiện chưa nổ bị phủ sau đó nổ tất cả đồng thời với bán kính $R-2$, và tiếp tục.

Tìm sức mạnh nhỏ nhất $R$ để một bò đáp nơi thích hợp gây nổ sau đó mọi kiện.

Dữ liệu vào

Dòng đầu chứa $N$ ($2 \leq N \leq 50,000$). $N$ dòng còn lại chứa số nguyên $x_1 \ldots x_N$, mỗi số trong $0 \ldots 1,000,000,000$.

Dữ liệu ra

In sức mạnh nhỏ nhất $R$ cho mọi kiện, làm tròn với đúng 1 chữ số sau dấu chấm thập phân.

Ví dụ

Dữ liệu vào 1

5
8
10
3
11
1

Dữ liệu ra 1

3.0

Ghi chú

Ví dụ sức mạnh 3 ở vị trí 5 làm nổ ngay 3 và 8. Chúng nổ đồng thời bán kính 2 phủ 1 và 10; chúng nổ đồng thời bán kính 1 phủ kiện cuối 11, rồi kiện ấy nổ bán kính 0.

Tác giả bài toán: Brian Dean