Balanced Weight Removal

We are given a horizontal rod of length (10^9) along which (N) distinct weights (each of unit mass) are attached. The (i)th weight is located at position (A_i) (its distance from the left end of the rod). Initially a box (or support) of width (w) is placed so that it supports the rod over an interval ([l, r]) (with (r=l+w) and (0 \le l < r \le 10^9)). You are allowed to choose (l) (and hence (r)) arbitrarily. Then, in (N-1) steps you remove one weight at a time; at each step you may only remove the leftmost or rightmost weight (with respect to their positions on the rod). Let the remaining weights at any stage have positions (b_1, b_2, \ldots, b_m) and center of mass [ C = \frac{b_1+b_2+\cdots+b_m}{m} ] The requirement is that at every stage (including the initial and final ones) the center (C) must lie within the fixed support interval ([l, r]).

Your task is to compute the minimum possible width (w) for the box such that there exists some choice of support ([l, r]) and an order of removals (always removing an extreme weight) with the property that the center of mass of the weights never leaves the interval ([l, r]).

It turns out that if we reverse the process (i.e. starting from a single weight and adding weights one by one to eventually form the entire set) then the only possible intermediate states are contiguous segments of the sorted array (A_1, A_2, \ldots, A_N) and their centers of mass are given by [ C(i,j)=\frac{A_i+A_{i+1}+\cdots+A_j}{j-i+1}, \quad 1\le i\le j\le N. ] The removal condition in the original process is equivalent to requiring that there exists a chain of contiguous segments from some singleton ([k,k]) up to ([1,N]) such that the overall range (i.e. the difference between the maximum and minimum center encountered in the chain) does not exceed (w).

Find the minimum such (w).

inputFormat

The first line contains an integer (N) (the number of weights). The second line contains (N) space‐separated integers (A_1, A_2, \ldots, A_N) (the positions of the weights). The positions are distinct and may be given in arbitrary order.

outputFormat

Output the minimum possible width (w) as a floating–point number with at least 6 digits after the decimal point.

sample

2
0 10

5.000000