题目描述

给定正整数数列 $h_1,h_2,\cdots,h_n$。设 $p$ 为 $1\sim n$ 的随机排列。

定义 $h'_i=h_{p_i}$。定义 $\mathrm{pre}_i$ 为最大的 $j\lt i$ 满足 $h'_j\ge h'_i$（如果不存在，规定为 $0$）。

求出 $\displaystyle \sum_{i=1}^n (i-\mathrm{pre}_i)$ 的期望值，保留两位小数输出。

输入格式

第一行一个正整数 $n$，表示数列长度。

第二行 $n$ 个正整数 $h_i$。

输出格式

输出一行一个实数，表示答案，保留两位小数。

3
3 2 1

4.33

提示

对于 $20\%$ 的数据，$1\leq n\leq 10$；

对于 $50\%$ 的数据，$1\leq n\leq 70$，且 $h_i$ 互不相同；

对于 $100\%$ 的数据，保证 $1\leq n\leq 300$，$1\leq h_i\leq 1000$。