Expected Sum of Non‐Crossing Graph Edge Weights on a Circle

Given n distinct points arranged on a circle in clockwise order, each point i is assigned a weight a_i. Consider the class of simple graphs (no self–loops or multiple edges) drawn on these points subject to the following rules:

• Any edge is drawn as a straight line (chord) connecting two distinct points.
• Two edges are allowed to share an endpoint; however, if two edges intersect at any point in their interiors they are said to be crossing and such a graph is not allowed (note that touching at endpoints is not considered crossing).
• An edge connecting two consecutive points on the circle (i.e. along the circular order) is considered a side and these edges never cross any other edge. They are optional: a graph may include none, some, or all of these edges.
• A graph with no edge (i.e. just n isolated vertices) is also considered valid.

For a valid graph, the weight of an edge connecting vertices i and j is defined as a_i \(\times\) a_j. All valid non–crossing graphs are considered equally likely. Compute the expected value of the sum of the edge weights taken over all valid non–crossing graphs on the circle.

Observation:

The key observation is that by linearity of expectation the expected sum is the sum for each potential edge (i,j) of its weight multiplied by the probability that it appears in a uniformly random valid (non–crossing) graph.

It turns out that:

• For any side (i.e. an edge connecting two consecutive vertices in clockwise order), the decision is independent (it can be chosen or not) so the probability is 1/2.
• For any chord that is not a side (i.e. vertices that are not consecutive on the circle), a combinatorial argument shows that its probability is 1/3.

Thus, if we denote

[ S = \sum_{i=1}^{n}a_i,a_{i+1}\quad\text{(with }a_{n+1}=a_1\text{)}, \quad D = \sum_{1 \le i < j \le n,, j\neq i+1 ; (\text{and }{i,j}\neq{1,n})}a_i,a_j, ]

then the expected sum is

[ E = \frac{1}{2},S + \frac{1}{3},D. ]

Input Format: The input starts with a positive integer n representing the number of points. The next line contains n integers a₁, a₂, \dots, a_n representing the weights of the points given in clockwise order.

Output Format: Output a single number — the expected sum of the edge weights. Answers within an absolute or relative error of 1e-6 will be accepted.

Example Explanation:

Example 1

Input:
3
1 2 3
Explanation:
Sides: (1,2), (2,3), (3,1) → weights: 12 + 23 + 3*1 = 11, each chosen with probability 1/2.
There is no chord (non–side) because in a triangle every edge is adjacent.
Expected sum = 11/2 = 5.5

</p>

Example 2

Input:
4
1 1 1 1
Explanation:
Sides: 4 edges, each with weight 1, probability = 1/2. Total from sides = 4*(1/2)= 2.0
Diagonals: There are 2 diagonals, each with weight 1, probability = 1/3. Total from diagonals = 2*(1/3)= 0.6666667
Expected sum = 2.0 + 0.6666667 = 2.6666667

</p>

inputFormat

The first line contains an integer n (1 ≤ n ≤ 10⁵) — the number of points on the circle. The second line contains n space–separated integers: a1 a2 ... an (0 ≤ a_i ≤ 10⁹), representing the weights of the points in clockwise order.

outputFormat

Output one real number — the expected sum of the weights of all edges in a graph drawn uniformly at random from all valid non–crossing graphs. Your answer will be accepted if its absolute or relative error does not exceed 10^-6.

sample

3
1 2 3

5.5