暂无测试数据。

虫群入侵了艾尔！高阶圣堂武士们要融合为一体，保卫他们的家园。现在有 $n$ 个高阶圣堂武士站成了一排，每个圣堂武士都有一个灵能值 $a_i$，两个相邻的圣堂武士可以融合成为一个新的圣堂武士，消耗的灵能为他们两个的灵能之和，同时这个新的圣堂武士的灵能也等于这两名圣堂武士的灵能之和。他们会不断融合直到最后只剩下一个人。现在大主教阿塔尼斯想知道，整个过程期望要消耗多少的灵能（每一次融合所以可能的融合都是等概率的）。

输入格式

第一行一个整数 $n$，代表圣堂武士的数量。

下一行 $n$ 个整数 $a_i$，代表初始时每个圣堂武士的灵能。

输出格式

一行一个小数，代表融合到只剩最后一人期望要消耗多少灵能，保留 $5$ 位小数。

数据规模

对于 $20\%$ 的数据：$n \le 3$。

对于 $40\%$ 的数据：$n \le 8$。

对于 $100\%$ 的数据：$n \le 1000$，$a_i$ 在 int 范围。

样例解释

对于第一个样例，一共可能的合并方案为：

1. 1 2 3 4 -> 3 3 4 -> 6 4 -> 10，$cost=3 + 6 + 10 = 19$。

2. 1 2 3 4 -> 3 3 4 -> 3 7 -> 10，$cost=3 + 7 + 10 = 20$。

3. 1 2 3 4 -> 1 5 4 -> 6 4 -> 10，$cost=5 + 6 + 10 = 21$。

4. 1 2 3 4 -> 1 5 4 -> 1 9 -> 10，$cost=5 + 9 + 10 = 24$。

5. 1 2 3 4 -> 1 2 7 -> 3 7 -> 10，$cost=7 + 3 + 10 = 20$。

6. 1 2 3 4 -> 1 2 7 -> 1 9 -> 10，$cost=7 + 9 + 10 = 26$。

每一种融合方案的概率都是 $\frac{1}{3}*\frac{1}{2}*\frac{1}{1}=\frac{1}{6}$，期望为 $(19+20+21+24+20+26)/6=130/6$

4
1 2 3 4

21.66667

10
13 5 34 6 4 2 76 2 90 100

1197.64603