题目描述

有一条由 $N$ 个格子组成的直线，格子编号为 $0,1,\ldots,N-1$，第 $i$ 个格子上写着金额 $v_i$。Bob 从格子 $0$ 开始。

游戏过程中，每次主持人要求 Bob 做决定时，他可以选择立刻结束游戏并获得当前格子上的金额，或者向右移动一格。

游戏开始前，主持人随机生成一个秘密整数 $K$，满足 $0\le K<N$。主持人最多让 Bob 向右移动 $K$ 次：如果 Bob 已经完成了第 $K$ 次向右移动且之前没有主动结束游戏，游戏立即结束，Bob 获得此时所在格子的金额。

Bob 不知道 $K$ 的具体分布，但知道它满足：对于每个正整数 $X$，都有

$\Pr(K<X)\le X/N$。

Bob 可以采用随机策略：当他到达每个格子时，自行规定在该格子主动停止的概率。Bob 希望在主持人选择对他最不利、但仍满足上述条件的 $K$ 的概率分布时，使自己的期望奖金尽可能大。

求这个最大化后的最坏情况期望奖金。

输入格式

第一行一个整数 $N$。

第二行包含 $N$ 个整数 $v_0,v_1,\ldots,v_{N-1}$。

输出格式

输出一个实数，表示 Bob 能保证的最大期望奖金。答案的绝对误差或相对误差不超过 $10^{-4}$ 即可。

数据范围

$1\le N\le50$；$0\le v_i\le10000$。

样例

5
1 2 3 4 5

3.0