Một thanh thẳng dài \(10^9\) được đặt theo chiều từ trái sang phải. Có thể bỏ qua khối lượng của thanh. Trên thanh gắn \(N\) quả cân, mỗi quả có khối lượng bằng \(1\), tại các vị trí đôi một khác nhau. Quả cân thứ \(i\) \((1 \le i \le N)\) ở vị trí \(A_i\), nghĩa là cách đầu trái của thanh một khoảng \(A_i\).

Ban đầu, bạn có một chiếc hộp rộng \(w\). Bạn đặt thanh lên hộp để hộp đỡ đoạn từ vị trí \(l\) đến vị trí \(r\), kể cả hai đầu, với \(0 \le l < r \le 10^9\) và \(r=l+w\). Sau đó, không được thay đổi \(l\) và \(r\).

Tiếp theo, mỗi lần bạn tháo quả cân ngoài cùng bên trái hoặc ngoài cùng bên phải còn gắn trên thanh. Bạn thực hiện thao tác này \(N-1\) lần. Trong toàn bộ quá trình, kể cả trạng thái ban đầu và trạng thái cuối cùng, trọng tâm của các quả cân còn trên thanh phải nằm trong đoạn \([l,r]\). Nếu còn \(m\) quả cân ở các vị trí \(b_1,b_2,\ldots,b_m\), vị trí trọng tâm là

Cho số quả cân \(N\) và các vị trí \(A_1,A_2,\ldots,A_N\), hãy tính chiều rộng nhỏ nhất có thể của hộp.

Dữ liệu vào

Đọc từ đầu vào chuẩn, tất cả các giá trị đều là số nguyên:

N
A_1 A_2 ... A_N

Dữ liệu ra

In một dòng chứa chiều rộng nhỏ nhất \(w\). Kết quả được chấp nhận nếu sai số tuyệt đối hoặc sai số tương đối không vượt quá \(10^{-9}\).

Kết quả phải có một trong hai dạng sau:

• Số nguyên, ví dụ 123, 0, -2022.
• Một số nguyên, tiếp theo là dấu chấm, rồi một dãy chữ số từ 0 đến 9, không có dấu phân cách hoặc khoảng trắng ở giữa. Không giới hạn số chữ số sau dấu chấm. Ví dụ 123.4, -123.00, 0.00288.

Ràng buộc

• \(2 \le N \le 200\,000\).
• \(0 \le A_1 < A_2 < \cdots < A_N \le 10^9\).

Chấm điểm

1. \(1\) điểm: \(N \le 20\)
2. \(33\) điểm: \(N \le 100\)
3. \(33\) điểm: \(N \le 2\,000\)
4. \(33\) điểm: Không có giới hạn bổ sung.

Ví dụ

3
1 2 4

0.8333333333

6
1 2 5 6 8 9

1.166666667

Nguồn

JOI Open Contest 2022, JCIOI. Bản dịch tiếng Việt theo CC BY-SA 4.0.