题目描述

设磁盘上有$\red{n }$个文件$\red{f_1, f_2,… , f_n}$，每个文件占磁盘上$\red{1}$个磁道。这$\red{n}$个文件的检索概率分别是$\red{p_1 ,p_2 ,…,p_n}$,且$\red{\displaystyle\sum_{i=1}^{n}p_i=1}$。磁头从当前磁道移到被检信息磁道所需的时间可用这$\red{2}$个磁道之间的径向距离来度量。如果文件$\red{f_i}$存放在第$\red{i}$道上,$\red{1≤i≤n}$，则检索这$\red{n}$个文件的期望时间是$\red{\displaystyle\sum_{1<=i<j<=n}p_ip_jd(i,j)}$。其中$\red{d(i,j)}$是第$\red{i}$道与第$\red{j}$道之间的径向距离$\red{|i-j|}$。磁盘文件的最优存储问题要求确定这$\red{n }$个文件在磁盘上的存储位置，使期望检索时间达到最小。

输入格式

第一行是正整数$\red{n}$，表示文件个数。第$\red{2}$ 行有$\red{n}$个正整数$\red{a_i}$，表示文件的检索概率。实际上第$\red{k}$个文件的检索概率应为$\red{a_k/\displaystyle\sum_{i=1}^{n}a_i}$。

输出格式

计算出最小期望检索时间（保留小数点后两位）。

样例

输入样例

5
33 55 22 11 9

输出样例

0．55