如今,大多数互联网广告都不是静态链接到网页的。相反,向打开网页的人显示的内容是在网页打开后 100 毫秒内确定的。通常,多家公司会在拍卖中争夺网页上的每个广告位。他们每个人都会收到一个包含有关用户、网页和广告位详细信息的请求,他们必须在这 100 毫秒内做出响应,并给出在该广告位上投放广告所需支付的出价。出价最高的公司赢得拍卖并可以投放广告。如果有多家公司并列最高出价,则随机选出获胜者。
但是,赢得拍卖的公司不必支付确切的出价金额。在大多数情况下,会使用第二价格拍卖。这意味着公司支付的金额等于为此广告位设置的所有其他出价的最高金额。
让我们考虑这样一个投标。有n家公司竞争投放广告。这些公司中的第 i 个将投标整数微美元,从 Li 和 Ri(含)之间的范围中等概率随机选择。换句话说,第 i 个公司的投标价值可以以相同的概率为 [Li, Ri] 范围内的任意整数。
确定获胜者在次价拍卖中必须支付的预期价值。
输入
输入的第一行包含一个整数 n (2 ≤ n ≤ 5)。接下来是 n 行,其中第 i 行包含两个数字 Li 和 Ri (1 ≤ Li ≤ Ri ≤ 10000),描述第 i 个公司的出价偏好。
这个问题没有子问题。正确提交将获得 8 分。
输出
输出绝对或相对误差不超过 1e - 9 的答案。
示例
输入 #1
3 4 7 8 10 5 5
输出 #1
5.7500000000
输入 #2
3 2 5 3 4 1 6
输出 #2
3.5000000000
注意
考虑第一个例子。第一家公司出价范围为 [4, 7] 内的随机整数微美元;第二家公司出价 8 到 10 美元,第三家公司出价 5 微美元。无论其出价的具体价格如何,第二家公司都将获胜,但其支付的价格取决于第一家公司的出价价值。以 0.5 的概率,第一家公司最多出价 5 微美元,整个拍卖的第二高价格将为 5。以 0.25 的概率,它将出价 6 微美元,以 0.25 的概率,它将出价 7 微美元。因此,第二家公司必须支付的预期值为 0.5·5 + 0.25·6 + 0.25·7 = 5.75。