Giải bài trực tuyến Học viện Công nghệ Bưu chính Viễn Thông

Hôm nay là một ngày đẹp trời nên T quyết định đi dạo quanh PTIT, vô tình T phát hiện ra Crush của mình đang tìm hiểu các dãy số, nên T quyết định lại gần bắt chuyện với Crush. Để có thể bắt chuyện được với Crush thì T phải giải quyết một bài toán như sau.

Crush của T định nghĩa:

• H là tổng các phần tử của 1 dãy con bất kỳ của 1 dãy A ban đầu hay $$H=\sum_{i=u}^{v}{A_i}$$với u, v  là điểm đầu và điểm cuối của dãy con.
• Điểm yếu của của 1 dãy là giá trị tuyệt đối lớn nhất của H.

Ban đầu bạn có một dãy có n số nguyên A = {a₁, a₂, ..., a_n}.

Xác định 1 số thực x sao cho điểm yếu của dãy B = {a₁ – x, a₂ – x,  ..., a_n – x} càng nhỏ càng tốt.

Crush yêu cầu T phải tìm ra giá trị điểm yếu càng nhỏ càng tốt của dãy A sau khi mỗi phần tử của A trừ đi 1 số thức x càng sớm thì sẽ đồng ý đi xem phim cùng mình.

Bạn hãy giúp T tìm ra câu trả lời nhé! Do đáp án là số thực nên hãy làm tròn 6 chữ số sau dấu phẩy.

Input

Dòng đầu tiên chứ số nguyên n (1 ≤ n ≤ 200000), là độ dài của dãy A.

Dòng tiếp theo chứ n số nguyên lần lượt là a₁, a₂, ..., a_n (|ai| ≤ 10000).

Output

Xuất ra số thực H cần tìm. Bạn hãy làm tròn 6 chữ số sau dấu phẩy.

Example

Input
3
1 2 3
10
1 10 2 9 3 8 4 7 5 6

Output
1.000000
4.500000

Giải thích

Trong ví dụ đầu tiên giá trị tối ưu x = 2 chuỗi B thu được là B = { -1, 0, 1}. Và cực đại thu được ở chuỗi con “-1” hoặc “1”  nên giá trị H = 1.000000.

Trong ví dụ thứ hai giá trị tối ưu x = 5.5 chuỗi B thu được là B = {-4.5, 4.5, -3.5, 3.5, -2.5, 2.5, -1.5, 1.5, -0.5, 0.5 } Và cực đại thu được ở chuỗi con “-4.5” hoặc “4.5”  nên giá trị H = 4.500000.