C. Аукцион второй цены
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

В наши дни большинство интернет-рекламы не привязано к веб-странице статически. Что именно будет показано пользователю, который открыл веб-страницу, решается в период 100 миллисекунд после открытия веб-страницы. Обычно за каждое рекламное место на странице соревнуются несколько компаний, и победитель решается посредством аукциона. Каждая из этих компаний получает запрос с информацией о пользователе, веб-странице и рекламном месте, а в ответ они посылают в течение 100 миллисекунд цену, которую они готовы заплатить, чтобы показать рекламу на этом рекламном месте. Компания, которая предлагает наивысшую цену, выигрывает аукцион и получает право показать свою рекламу. Если несколько компаний предложили максимальную цену, победитель выбирается случайным образом.

Компания, выигравшая аукцион, не всегда должна заплатить ровно столько, сколько она предложила. В большинстве случаев используется аукцион второй цены. Это значит, что победитель аукциона должен заплатить максимум из всех предложенных на аукционе цен, кроме своей.

Рассмотрим такой аукцион. Есть n компаний, которые соревнуются за рекламное место. i-я из этих компаний заявит случайное целое количество микродолларов, равновероятно распределённое на отрезке от Li до Ri включительно. Иными словами, каждое целое значение от Li до Ri имеет одинаковую вероятность быть выбранным i-й компанией.

Определите математическое ожидание цены, которую заплатит победитель при аукционе второй цены.

Входные данные

В первой строке записано единственное целое число n (2 ≤ n ≤ 5). Далее следуют n строк, на i-й из которых находятся два целых числа Li и Ri (1 ≤ Li ≤ Ri ≤ 10000), описывающие отрезок цен i-й компании.

В этой задаче нет подзадач. За ее решение вы получите 8 баллов.

Выходные данные

Выведите ответ на задачу с абсолютной или относительной погрешностью не более чем 1e - 9.

Примеры
Входные данные
3
4 7
8 10
5 5
Выходные данные
5.7500000000
Входные данные
3
2 5
3 4
1 6
Выходные данные
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.