配点: 5 点
問題文
数列爱好者高桥君制作了长度为 N 序列 使用 a 的序列。该序列通过从 a 可以得到第 i 第一个元素 a_i 的值为 独立于小于L_i 以上 R_i 下面 整数 中均匀随机选择决定。
这样得到的序列 a 的逆序数的期望值请计算。
另外,长度为 m 序列 使用 x 的“逆序数”指的是i < j 和 x_i > x_j 似乎是 (i, j) (1 \leq i, j \leq m) 的号码。
制約
- 1 \leq N \leq 100
- 1 \leq L_i \leq R_i \leq 100 (1 \leq i \leq N)
- 所有输入均以整数形式给出
入力
输入是按以下格式从标准输入给出的。
N L_1 R_1 \vdots L_N R_N
出力
请输出答案。不过,相对误差或绝对误差为 10^{-7} 如果答案如下,则视为正确。
入力例 1
2 1 2 1 2
出力例 1
0.250000000000
数列 a 的可能有如下 4 是的。 请注意,我们正在寻找除以
- a = (1, 1), 転倒数 0
- a = (1, 2), 転倒数 0
- a = (2, 1), 転倒数 1
- a = (2, 2), 転倒数 0
因此,期望值是 \frac{1}{4} = 0.25 。 对于
入力例 2
3 3 3 1 1 4 4
出力例 2
1.000000000000
数列 a 是 a = (3, 1, 4) 唯一的,这个数列的逆序数是 1 。
入力例 3
10 1 10 38 40 8 87 2 9 75 100 45 50 89 92 27 77 23 88 62 81
出力例 3
13.696758921226