Permutation Bo

Problem 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

Author

绍兴一中

Source

2016 Multi-University Training Contest 3