A straight stick of length ~10^9~ is placed from the left to the right. You can ignore the weight of the stick. In total, ~N~ unit weights are attached to the stick. The positions of the ~N~ weights are different from each other. The position of the ~i~-th weight ~(1 \le i \le N)~ is ~A_i~, i.e., the distance between the ~i~-th weight and the leftmost end of the stick is ~A_i~.

In the beginning, we have a box of width ~w~. We place the stick on the box so that the box supports the range from ~l~ to ~r~ of the stick ~(0 \le l < r \le 10^9)~, inclusive, i.e., the range of the stick from the point whose position is ~l~ to the point whose position is ~r~. Here, ~r = l+w~ is satisfied. We cannot change the values of ~l~ and ~r~ afterward.

Next, among the weights attached to the stick, we remove the leftmost one or the rightmost one. We shall repeat this operation ~N-1~ times. In this process, including the initial state and the final state, the barycenter of the weights attached to the stick should remain in the range from ~l~ to ~r~, inclusive. Here, if ~m~ weights are attached to the stick whose positions are ~b_1, b_2, \dots, b_m~, the position of the barycenter is ~\frac{b_1+b_2+\dots+b_m}{m}~.

Given the number of weights ~N~ and the positions of the weights ~A_1, A_2, \dots, A_N~, write a program which calculates the minimum possible width ~w~ of the box.

Input Specification

Read the following data from standard input. Given values are all integers.

~N~

~A_1\ A_2 \dots A_N~

Output Specification

Write one line to the standard output. The output should contain the minimum possible width ~w~ of the box. Your program is considered correct if the relative error or the absolute error of the output is less than or equal to ~10^{-9}~. The format of the output should be one of the following.

• Integer. (Example: ~123~, ~0~, ~-2022~)
• A sequence consisting of an integer, the period, a sequence of numbers between ~0~ and ~9~. The numbers should not be separated by symbols or spaces. There is no restriction on the number of digits after the decimal point. (Example: ~123.4~, ~-123.00~, ~0.00288~)

Constraints

• ~2 \le N \le 200\,000~.
• ~0 \le A_1 < A_2 < \dots < A_N \le 10^9~.

Subtasks

1. (1 point) ~N \le 20~.
2. (33 points) ~N \le 100~.
3. (33 points) ~N \le 2\,000~.
4. (33 points) No additional constraints.

Sample Input 1

3
1 2 4

Sample Output 1

0.8333333333

Explanation for Sample 1

Let the width of the box be ~\frac{5}{6}~. We put ~l = \frac{3}{2}~, ~r = \frac{7}{3}~. We perform the following operations.

• In the beginning, the position of the barycenter is ~\frac{7}{3}~.
• In the first operation, we remove the rightmost weight (the weight whose position is ~4~). Then the barycenter becomes ~\frac{3}{2}~.
• In the second operation, we remove the leftmost weight (the weight whose position is ~1~). Then the barycenter becomes ~2~.

In this process, the barycenter remains in the range from ~l~ to ~r~. Since the width of the box cannot be smaller than ~\frac{5}{6}~, output ~\frac{5}{6}~ in a decimal number.

This sample input satisfies the constraints of all the subtasks.

Sample Input 2

6
1 2 5 6 8 9

Sample Output 2

1.166666667

This sample input satisfies the constraints of all the subtasks.