AT_past17_n.ソフトウェアアップデート

高桥打算更新 $N$ 个应用，编号分别为 app $1$，app $2$，$\ldots$，app $N$。
更新第 $i$ 个应用（$1\leq i\leq N$）需要 $T_i$ 单位时间。

高桥可以自选应用的更新顺序。
从时间 $0$ 开始，他的电脑会按照指定顺序逐个更新应用。
具体来说，若他选择第 $i$ 个被更新的应用为 app $p_i$，则电脑会按如下方式工作：

• 第 $k$ 个被更新的应用 app $p_k$，会从时间 $(T_{p_1}+T_{p_2}+\cdots+T_{p_{k-1}})$ 开始更新，到 $(T_{p_1}+T_{p_2}+\cdots+T_{p_{k-1}}+T_{p_k})$ 结束。

他想要选择合适的顺序，使得在更新过程中查看进度时，能尽可能准确地估算全部更新所需的总时长。

然而，在更新过程中，他只能获得一个整数 $k$，表示当前正在进行第 $k$ 次更新。
若他发现自己在时间 $t$ 正处于第 $k$ 次更新，则他对于总更新时长的估算为 $f(t)=\frac{N}{k-0.5}\cdot t$。
其中，在第 $i$ 次更新刚开始时，他认为正在进行第 $i$ 次更新。具体地，在时间 $0$ 时，他认为正在进行第 $1$ 次更新；每当第 $i$ 次更新结束并且第 $(i+1)$ 次更新开始时，他认为正在进行第 $(i+1)$ 次更新。

记全部更新的总时长为 $S=\sum_{i=1}^N T_i$。
假设他在 $t$ 时刻进行估算，其中 $t$ 从 $0$（包含）到 $S$（不包含）之间均匀随机选择，求在最优顺序下，他估算误差 $\lvert f(t)-S\rvert$ 的期望值的最小值。

输入按以下格式从标准输入读入：

$N$ $T_1$ $T_2$ $\ldots$ $T_N$

请输出最小期望值 $\lvert f(t)-S\rvert$。
当你的答案与正确答案的绝对误差或相对误差不超过 $10^{-6}$ 时，将被判定为正确。

样例解释 1

全部更新所需总时长为 $S=3+7=10$。
若指定更新顺序为 $1\to 2$，在 $0\leq t<10$ 时，他对总时长 $f(t)$ 的估算如下：

• $0\leq t<3$ 时，$f(t)=\frac{2}{1-0.5}\cdot t=4t$；
• $3\leq t<10$ 时，$f(t)=\frac{2}{2-0.5}\cdot t=\frac{4}{3}t$。

当 $t$ 在 $0\leq t<10$ 范围内等概率随机选取时，$\lvert f(t)-S\rvert$ 的期望为 $\frac{46}{15}=3.066\cdots$，这是可能达到的最小值。

样例解释 2

如果指定顺序为 $1\to 3\to 2$，则 $\lvert f(t)-S\rvert$ 的期望取最小值。

数据范围

• $2\leq N\leq 18$
• $1\leq T_i\leq 10^6$
• 所有输入值均为整数。

由 ChatGPT 5 翻译