E. 期望个数统计

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较

题目描述

某互联网公司一年一度的春招开始了,一共有 n 名面试者入选。每名面试者都会提交一份简历,公司会根据提供的简历资料产生一个预估的能力值,数值越大代表越有可能通过面试。

小 A 和小 B 负责审核面试者,他们均有所有面试者的简历,并且将各自根据面试者能力值从大到小的顺序浏览。由于简历事先被打乱过,能力值相同的简历的出现顺序是从它们的全排列中等可能地取一个。现在给定 n 名面试者的能力值 scores ,设 X 代表小 A 和小 B 的浏览顺序中出现在同一位置的简历数,求 X 的期望。

提示:离散的非负随机变量的期望计算公式为 E(X) = \sum_{k=1}^\infty k Pr(X=k) 。在本题中,由于 X 的取值为 0 到 n 之间,期望计算公式可以是 E(X) = \sum_{k=1}^n k Pr(X=k) 。 显然, 这道题中,该期望值是一个整数。

输入格式

输入共 2 行。

第一行一个整数 n . 代表面试者的个数。

第二行 n 个整数, 代表每个面试者的能力值。

输出格式

输出仅一个整数, 所求 X 的期望值。

样例

样例输入 1

3
1 2 3

样例输出 1

3

样例输入 2

3
1 2 2

样例输出 2

2

数据范围与提示

对于 30\% 的数据, n \leq 1000 .

对于 100\% 的数据, 1 \leq n \leq 5 \cdot 10^5, 1 \leq score \leq 10^9

本题源自: 力扣杯 2020 全国春季大赛战队赛 第1题

原题链接:期望个数统计