CF513C.Second price auction

Nowadays, most of the internet advertisements are not statically linked to a web page. Instead, what will be shown to the person opening a web page is determined within 100 milliseconds after the web page is opened. Usually, multiple companies compete for each ad slot on the web page in an auction. Each of them receives a request with details about the user, web page and ad slot and they have to respond within those 100 milliseconds with a bid they would pay for putting an advertisement on that ad slot. The company that suggests the highest bid wins the auction and gets to place its advertisement. If there are several companies tied for the highest bid, the winner gets picked at random.

However, the company that won the auction does not have to pay the exact amount of its bid. In most of the cases, a second-price auction is used. This means that the amount paid by the company is equal to the maximum of all the other bids placed for this ad slot.

Let's consider one such bidding. There are n companies competing for placing an ad. The i-th of these companies will bid an integer number of microdollars equiprobably randomly chosen from the range between L__i and R__i, inclusive. In the other words, the value of the i-th company bid can be any integer from the range [L__i, R__i] with the same probability.

Determine the expected value that the winner will have to pay in a second-price auction.

如今，大多数互联网广告并非静态链接到网页上。相反，当用户打开一个网页时，实际展示给该用户的广告内容会在网页打开后的 100 毫秒内动态决定。通常，多个公司会就网页上的每个广告位展开竞拍。每家公司都会收到一个请求，其中包含有关用户、网页及该广告位的详细信息；它们必须在 100 毫秒内响应，提交自己愿意为在该广告位投放广告而支付的出价（即“竞价”）。出价最高的公司赢得竞拍，并获得在该广告位投放广告的权利。若存在多个公司并列最高出价，则随机从中选取一名胜者。

然而，赢得竞拍的公司并不需要按其自身所报出价全额付款。在大多数情况下，采用的是第二价格拍卖（second-price auction）机制。这意味着该公司实际支付的金额等于其余所有公司对该广告位所报出价中的最高值。

现考虑这样一场竞拍：共有 $n$ 家公司参与竞争。其中第 $i$ 家公司的出价是一个在区间 $[L_i,\,R_i]$ 内等概率随机选取的整数（单位：微美元）。换言之，第 $i$ 家公司的出价可以是区间 $[L_i,\,R_i]$ 中任意一个整数，且各整数被选中的概率相等。

请计算在第二价格拍卖机制下，获胜者所需支付金额的期望值。

The first line of input contains an integer number n (2 ≤ n ≤ 5). n lines follow, the i-th of them containing two numbers L__i and R__i (1 ≤ L__i ≤ R__i ≤ 10000) describing the i-th company's bid preferences.

This problem doesn't have subproblems. You will get 8 points for the correct submission.

输入的第一行包含一个整数 $ n $（$ 2 \leq n \leq 5 $）。接下来有 $ n $ 行，其中第 $ i $ 行包含两个数 $ L_i $ 和 $ R_i $（$ 1 \leq L_i \leq R_i \leq 10000 $），描述第 $ i $ 家公司的报价偏好。

本题没有子问题。正确提交可获得 8 分。

Output the answer with absolute or relative error no more than 1_e_ - 9.

以绝对或相对误差不超过 $10^{-9}$ 输出答案。

Consider the first example. The first company bids a random integer number of microdollars in range [4, 7]; the second company bids between 8 and 10, and the third company bids 5 microdollars. The second company will win regardless of the exact value it bids, however the price it will pay depends on the value of first company's bid. With probability 0.5 the first company will bid at most 5 microdollars, and the second-highest price of the whole auction will be 5. With probability 0.25 it will bid 6 microdollars, and with probability 0.25 it will bid 7 microdollars. Thus, the expected value the second company will have to pay is 0.5·5 + 0.25·6 + 0.25·7 = 5.75.

考虑第一个例子。第一家公司的出价是在区间 $[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$。