Expected Sum of Differences

Given a sequence of n positive integers \(h_1, h_2, \ldots, h_n\). Consider a random permutation \(p\) of \(\{1, 2, \ldots, n\}\), and define a new sequence \(h'_i = h_{p_i}\) for \(1 \le i \le n\). For each \(i\), let \(\mathrm{pre}_i\) denote the largest index \(j < i\) such that \(h'_j \ge h'_i\) (if no such \(j\) exists, define \(\mathrm{pre}_i=0\)).

Your task is to compute the expected value of the sum

[ S = \sum_{i=1}^n (i-\mathrm{pre}_i) ]

over all possible permutations \(p\) and output the result rounded to two decimal places.

Note: The original sequence \(h_1, h_2, \ldots, h_n\) may contain duplicate values. It can be shown that the expected value can be computed by the formula:

[ E[S] = \sum_{i=1}^n \frac{n+1}{c_i+1}, ]

where for each \(i\), \(c_i\) is the number of elements in \(\{h_1, h_2, \ldots, h_n\}\) that are \(\ge h_i\). (When all numbers are distinct, one may check that \(\frac{n+1}{c_i+1\,}\) equals the harmonic number \(H_i\), giving \(E[S] = H_1+H_2+\cdots+H_n\).)

inputFormat

The input consists of two lines:

• The first line contains a single integer \(n\) representing the number of elements.
• The second line contains \(n\) positive integers \(h_1, h_2, \ldots, h_n\) separated by spaces.

outputFormat

Output the expected value of \( \sum_{i=1}^n (i-\mathrm{pre}_i) \) rounded to two decimal places.

sample

2
1 1

2.00