Permutation Bo

题目连接：

Description

There are two sequences h1∼hn and c1∼cn. h1∼hn is a permutation of 1∼n. particularly, h0=hn+1=0.

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

Define the function f(h)=∑ni=1ci[hi>hi−1 and hi>hi+1]

Bo have gotten the value of c1∼cn, 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≤n≤1000), second line contains n non-negative integer ci(0≤ci≤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

题意

给你c数组，如果h[i]>h[i-1]和h[i]>h[i+1]，答案就加上c。

h是1-n的排列，h[0]=0,h[n+1]=0

然后求最后答案的期望是多少

题解：

根据期望的线性性，我们可以分开考虑每个位置对答案的贡献。

可以发现当ii不在两边的时候和两端有六种大小关系，其中有两种是对答案有贡献的。

那么对答案的贡献就是\(\frac{c_i}{3}\)

在两端的话有两种大小关系，其中有一种对答案有贡献。

那么对答案的贡献就是\(\frac{c_i}{2}\)

复杂度是O(n)。

注意特判n=1的情况。

代码

#include
    
     using namespace std;const int maxn = 1005;int n;int c[maxn];void solve(){    for(int i=1;i<=n;i++)        scanf("%d",&c[i]);    if(n==1){        double ans = c[1];        printf("%.12f\n",ans);        return;    }    if(n==2){        double ans = (c[1]+c[2])/2.0;        printf("%.12f\n",ans);        return;    }    double ans = 0;    for(int i=2;i