Background

Translated from JOI Open 2022 T1. シーソー / Seesaw.

Problem Description

A straight rod of length ${10}^9$ is placed horizontally from left to right. You may ignore the weight of the rod. There are $N$ weights hanging on the rod, each with unit mass. The positions of these $N$ weights are all distinct. The position of the $i$-th weight ($1 \le i \le N$) is $A_i$. That is, the distance from the left end of the rod to the $i$-th weight is $A_i$.

At the beginning, we have a box of width $w$. We can place the rod on the box so that the box supports the part of the rod from $l$ to $r$ ($0 \le l < r \le {10}^9$), inclusive of both ends; that is, the interval on the rod from position $l$ to position $r$. Here we must have $r = l + w$. After that, we are not allowed to change the values of $l$ and $r$.

Next, we remove the leftmost or the rightmost weight hanging on the rod. We need to repeat this operation $N - 1$ times. During this process, including the initial state and the final state, the center of mass of all weights hanging on the rod must always stay between $l$ and $r$, inclusive. If there are $m$ weights on the rod at positions $b_1, b_2, \ldots, b_m$, then the center of mass is at $\frac{b_1 + b_2 + \cdots + b_m}{m}$.

Given $N$ and the positions $A_1, A_2, \ldots, A_N$ of the $N$ weights, write a program to compute the minimum possible width $w$ of the box.

Input Format

The first line contains a positive integer $N$.

The second line contains $N$ non-negative integers $A_1, A_2, \ldots, A_N$.

Output Format

Output the minimum possible width $w$ of the box. Your program will be judged correct if the absolute error or relative error between your output and the standard answer is at most ${10}^{-9}$.

3
1 2 4

0.8333333333

6
1 2 5 6 8 9

1.166666667

Hint

[Sample Explanation #1]

The width of the box can be $\frac{5}{6}$. Let $l = \frac{3}{2}, r = \frac{7}{3}$. Do the following operations:

• Initially, the center of mass is at $\frac{7}{3}$.
• In the first operation, we remove the rightmost weight (the weight at position $4$). The center of mass becomes $\frac{3}{2}$.
• In the second operation, we remove the leftmost weight (the weight at position $1$). The center of mass becomes $2$.

During this process, the center of mass always stays within the range from $l$ to $r$.

Since the width of the box cannot be less than $\frac{5}{6}$, output the decimal form of $\frac{5}{6}$.

This sample satisfies the constraints of all subtasks.

[Sample Explanation #2]

This sample satisfies the constraints of all subtasks.

[Constraints]

This problem uses bundled testdata.

• Subtask 1 (1 point): $N \le 20$.
• Subtask 2 (33 points): $N \le 100$.
• Subtask 3 (33 points): $N \le 2000$.
• Subtask 4 (33 points): no additional constraints.

For all testdata, $2 \le N \le 2 \times 10^5$, $0 \le A_1 < A_2 < \cdots < A_N \le {10}^9$.

Translated by ChatGPT 5