Sereja and Dividing

2000ms

262144K

Description:

Let's assume that we have a sequence of doubles a₁, a₂, ..., a_|a| and a double variable x. You are allowed to perform the following two-staged operation:

choose an index of the sequence element i (1 ≤ i ≤ |a|);
consecutively perform assignments: $\text{[math]}$ .

Let's use function g(a, x) to represent the largest value that can be obtained from variable x, using the described operation any number of times and sequence a.

Sereja has sequence b₁, b₂, ..., b_|b|. Help Sereja calculate sum: $\text{[math]}$ . Record [b_i, b_i + 1, ..., b_j] represents a sequence containing the elements in brackets in the given order. To avoid problems with precision, please, print the required sum divided by |b|².

Input:

The first line contains integer |b| (1 ≤ |b| ≤ 3·10⁵) — the length of sequence b. The second line contains |b| integers b₁, b₂, ..., b_|b| (1 ≤ b_i ≤ 10⁵).

Output:

In a single line print a real number — the required sum divided by |b|². Your answer will be considered correct if its absolute or relative error won't exceed 10^- 6.

Sample Input:

5
1 2 3 4 1

Sample Output:

1.238750000000000

Informação

Provedor Codeforces

Código CF380E