题目描述

すぬけ君占卜了明天的运势。结果显示，在 $N$ 个场景中，将等概率发生其中一个，在第 $i$ 个场景下，他会损失 $A_i$ 日元。

因此，すぬけ君决定今天购买保险。如果他向保险公司支付 $x$ 日元，当他损失 $A_i$ 日元时，将获得 $\min(A_i,2x)$ 日元的补偿。这里，$x$ 可以选择任意非负实数。

すぬけ君希望最小化自己最终损失金额（$=x+A_i-\min(A_i,2x)$）的期望值。请你求出这个最小期望值。

输入格式

输入通过标准输入给出，格式如下：

$N$ $A_1$ $A_2$ $\cdots$ $A_N$

输出格式

请输出答案。如果绝对误差或相对误差不超过 $10^{-6}$，则判定为正确。

样例 1

输入

3
3 1 4

输出

1.83333333333333333333

样例 2

输入

10
866111664 178537096 844917655 218662351 383133839 231371336 353498483 865935868 472381277 579910117

输出

362925658.10000000000000000000

说明/提示

限制条件

• $1 \leq N \leq 10^5$
• $1 \leq A_i \leq 10^9$
• 输入的所有数值均为整数

样例解释 1

选择 $x=1.5$ 是最优的。支付 $1.5$ 日元后，以下 $3$ 个场景等概率发生：

• 场景 $1$：损失 $3$ 日元后，获得 $\min(3,2x)=3$ 日元补偿。最终损失金额为 $x+A_1-\min(A_1,2x)=1.5+3-3=1.5$ 日元。
• 场景 $2$：损失 $1$ 日元后，获得 $\min(1,2x)=1$ 日元补偿。最终损失金额为 $x+A_2-\min(A_2,2x)=1.5+1-1=1.5$ 日元。
• 场景 $3$：损失 $4$ 日元后，获得 $\min(4,2x)=3$ 日元补偿。最终损失金额为 $x+A_3-\min(A_3,2x)=1.5+4-3=2.5$ 日元。

因此，损失金额的期望为 $(1.5+1.5+2.5)/3=1.833333\cdots$。

由 ChatGPT 4.1 翻译