P10668 BZOJ2720 [Violet 5] Queueing for a Spring Outing

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.

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 one real number in one line, which is the answer rounded to two decimal places.

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