环绕修复

择枝完了，但管道需要修复——环绕修复。

"修复？"CC问。

"对。"你说，"$n$个点排成一个环，每段管道有一个损坏度。选一个起点，顺时针修复，求最小总代价。"

"代价？"

"对。"你说，"修复一段管道的代价等于当前已修复的管道数乘以损坏度。"

"当前已修复？"

"对。"你说，"修的越多，后面每段代价越高——因为工具越来越重。"

"咋算？"

"断环。"你说，"把环断开，枚举起点，然后用前缀和优化。"

"前缀和？"

"对。"你说，"先算损坏度的前缀和，然后总代价可以表示为前缀和的组合。"

"第47段。"你说，"损坏度47——如果排在前面修，代价小；排在后面，代价大。"

"排哪？"

"从小到大。"你说，"先修损坏度小的，后修大的。"

"贪心？"

"对。"你说，"先易后难——小的先修，积累工具；大的后修，但此时工具已经够多。"

"像干活？"

"对。"你说，"像干活——先干轻松的，热身；再干重的，有劲。"

"如果先干重的？"

"累。"你说，"一开始就累，后面干不动了。"

"累坏？"

"对。"你说，"总代价可能更大。"

CC看着那个环——像一条腰带，像一条轨道，像某种需要一圈一圈修的东西。

"一圈修完？"她问。

"对。"你说，"从某点开始，绕一圈，回到起点。"

"回得来？"

"对。"你说，"环没有终点，只有起点。"

Echo把修复过程投射出来——一段一段变绿，像春天，像愈合。

"以前管道是断的。"她说，"现在……连上了。"

"因为你在修。"CC说。

"对。"Echo说，"因为我在修。

题目描述

$n$段管道排成环，第$i$段损坏度$a_i$。从某点开始顺时针修复，修复第$k$段的代价为$k\times a_i$。求最小总代价。

输入格式

第一行$n$。第二行$n$个整数$a_i$。

输出格式

最小总代价。

输入样例

20 20
15 12

输出样例

19.9788

提示

• 断环成链，枚举起点。
• 排序后从小到大修复。
• 前缀和优化计算总代价。