25422번 - Seesaw 서브태스크스페셜 저지다국어

문제

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ドル ≤ i ≤ 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ドル ≤ l < r ≤ 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+\cdots +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.

입력

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

$N$

$A_1, A_2, \cdots , A_N$

출력

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 0ドル.000,000円,001円$ ($= 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$)

제한

• 2ドル ≤ N ≤ 200,000円$.
• 0ドル ≤ A_1 < A_2 < \cdots < A_N ≤ 1,000円,000円,000円$ ($= 10^9$).

서브태스크

힌트