Problem Description

Given a sequence of positive integers $h_1,h_2,\cdots,h_n$. Let $p$ be a random permutation of $1\sim n$.

Define $h'_i=h_{p_i}$. Define $\mathrm{pre}_i$ as the largest $j\lt i$ such that $h'_j\ge h'_i$ (if it does not exist, let it be $0$).

Find the expected value of $\displaystyle \sum_{i=1}^n (i-\mathrm{pre}_i)$, and output it rounded to two decimal places.

Input Format

The first line contains a positive integer $n$, which is the length of the sequence.

The second line contains $n$ positive integers $h_i$.

Output Format

Output one real number in one line, which is the answer rounded to two decimal places.

3
3 2 1

4.33

Hint

For $20\%$ of the testdata, $1\leq n\leq 10$.

For $50\%$ of the testdata, $1\leq n\leq 70$, and all $h_i$ are distinct.

For $100\%$ of the testdata, it is guaranteed that $1\leq n\leq 300$ and $1\leq h_i\leq 1000$.

Translated by ChatGPT 5