Logo Quest Online Judge

QOJ

时间限制:2 s 空间限制:512 MB
统计

题目描述

小C虽然没有参加NOI2016, 但当他看到"国王饮水记"这题时还是迅速秒掉了.

小C认为这题太水了,于是他决定对这题进行加强.

现在小C桌上有 $n$ 杯水排成一行,第 $i$ 杯水中有$w_i$ 单位体积的水. 他会选择一个区间$[l,r]$ ,并拿一个初始为空的杯子(杯子的容积无限大),他可以重复无限次以下操作:

• 选定任意一杯水$i$,$i \in [l, r]$.

• 使 $i$ 和它拿着的杯子里的水的体积变为它们的平均值.

小C希望进行若干操作后最大化杯子里的水的体积,设 $g(l, r)$ 为这个最大值.你需要求:

$$\sum_{i=1}^{n}\sum_{r=l}^{n}\frac{g(l,r)}{n^2}$$

输入格式

第一行一个整数 $n$.

第二行 $n$ 个整数,第 $i$ 个为$w_i$.

输出格式

输出一个实数表示答案.

你的答案被认为是正确的,当且仅当其与标准答案的绝对误差不超过 $10^{-2}$.

样例

样例输入

5
1 2 3 4 1

样例输出

1.238750000000000

数据范围与提示

对于所有数据,有 $1 \leq w_i \leq 10^5$.

• subtask1$(10\%)$, $n \leq 5$.

• subtask2$(15\%)$, $n \leq 100$.

• subtask3$(15\%)$, $n \leq 1500$.

• subtask4$(10\%)$, $n \leq 10^4$.

• subtask5$(20\%)$, $n \leq 5 \times 10^4$.

• subtask6$(30\%)$, $n \leq 10^6$.