Permutation Bo

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 131072/131072 K (Java/Others)

Description

There are two sequences $h_1\sim h_n$ and $c_1\sim c_n$. $h_1\sim h_n$ is a permutation of $1\sim n$. particularly, $h_0=h_{n+1}=0$.

We define the expression $[condition]$ is 1 when $condition$ is True,is 0 when $condition$ is False.

Define the function $f(h)=\sum_{i=1}^{n}{c_i[h_i>h_{i-1}~~and~~h_i>h_{i+1}]}$

Bo have gotten the value of $c_1\sim c_n$, and he wants to know the expected value of $f(h)$.

Input

This problem has multi test cases(no more than $12$).

For each test case, the first line contains a non-negative integer $n(1\leq n\leq1000)$, second line contains $n$ non-negative integer $c_i(0\leq c_i\leq 1000)$.

Output

For each test cases print a decimal - the expectation of $f(h)$.

If the absolute error between your answer and the standard answer is no more than $10^{-4}$, your solution will be accepted.

Sample Input

4 3 2 4 5 5 3 5 99 32 12

Sample Output

6.000000 52.833333

Hint

wange2014

Source

2016 Multi-University Training Contest 3

提交代码