Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

P193PROB - Problem B - Điểm yếu và giá trị H

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 = {a1, a2, ..., an}.

Xác định 1 số thực x sao cho điểm yếu của dãy B = {a1 – x, a2 – x,  ..., an – 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à a1, a2, ..., an (|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.


Được gửi lên bởi:adm
Ngày:2019-03-01
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:ASM32-GCC ASM32 ASM64 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL6 PERL PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.