Độ Lệch Đoạn Liên Tiếp

Cho dãy $a$ . Chọn số thực $x$ , thay mỗi phần tử bằng $a_{i} - x$ . Độ lệch là trị tuyệt đối lớn nhất của tổng một đoạn liên tiếp không rỗng. Hãy chọn $x$ để độ lệch nhỏ nhất.

Input

$n$ , rồi $n$ số $a_{i}$ .

Output

In minimum, sai số $1 0^{- 6}$ .

Constraints

$1 \leq n \leq 2 \cdot 1 0^{5}$ .
$- 1 0^{4} \leq a_{i} \leq 1 0^{4}$ .

Scoring

Subtask $1$ ( $50$ điểm): $n \leq 1000$ .
Subtask $2$ ( $50$ điểm): đầy đủ.

Example

Test 1

Input

2
0 2

Output

1.000000000000000

Giải thích: $x = 1$ tạo $- 1, 1$ ; mọi tổng đoạn có trị tuyệt đối không quá $1$ .

Lời giải tóm tắt

Ý tưởng: Mỗi tổng đoạn là S-len·x; trị tuyệt đối là maximum hai hàm affine. Maximum trên mọi đoạn là hàm lồi F(x). Đánh giá F bằng Kadane cho tổng dương lớn nhất của a_i-x và cho tổng âm lớn nhất qua dãy đối dấu.
Ý tưởng: Tam phân [min a,max a] trong 100 vòng. Tính lồi bảo đảm mỗi bước giữ một đáy. Độ phức tạp O(100n), bộ nhớ O(n).