← 返回题单
题单练习 概率与期望
← 上一题 下一题 →

A7097 | 列队春游

时间限制1s
内存限制128MB
通过 / 提交0/0

题目描述

给定正整数数列 $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$。

输出格式

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

输入输出样例

输入 #1
3
3 2 1
输出 #1
4.33
C++ 编辑器
输入
输出