#CS1728. 逆序对概率

逆序对概率

题目背景

翻译自 CSES-1728 题。

题目描述

给定一个包含 n 个整数的数组 x1,x2,…,xnx_1, x_2, \dots, x_nx1​,x2​,…,xn​，每个整数 xix_ixi​ 独立地从 1 到 rir_iri​ 的范围内随机选择。一个逆序对是指一对索引 (a,b)(a, b)(a,b)，其中 a<ba < ba<b 且 xa>xbx_a > x_bxa​>xb​。

请计算该数组中逆序对的预期数量。

输入格式

第一行输入一个整数 n：表示数组的大小。

第二行输入 n 个整数 r1,r2,…,rnr_1, r_2, \dots, r_nr1​,r2​,…,rn​：分别表示每个位置上可能值的范围。

输出格式

输出数组中逆序对的预期数量，保留六位小数（四舍五入）。

样例

3
5 2 7

1.057143

说明/提示

$1\leq n \leq 100$

1≤ri≤1001 \leq r_i \leq 1001≤ri​≤100。