L2. Температурные зоны (сложная версия)
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это сложная версия задачи. Лёгкая и сложная версии отличаются только ограничениями входных данных. Каждая версия засчитывается как отдельная задача.

На научной станции исследуют температурные условия. Известны $$$2n$$$ различных целых значений температуры $$$x_1 \lt x_2 \lt \ldots \lt x_{2n}$$$.

Они задают $$$n$$$ непересекающихся диапазонов: $$$[x_1,x_2]$$$, $$$[x_3,x_4]$$$, ..., $$$[x_{2n-1},x_{2n}]$$$. Исследователя интересуют все целые температуры, попавшие хотя бы в один из этих диапазонов. Найдите их среднее арифметическое.

Целое число $$$x$$$ принадлежит диапазону $$$[l,r]$$$, если $$$l\le x\le r$$$.

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

В первой строке находится единственное натуральное число n ($$$1 \le n \le 10^5$$$). В следующих $$$2n$$$ строках записано по одному целому числу: $$$x_1, x_2, \ldots, x_{2n}$$$ ($$$|x_i| \le 10^9$$$ для всех $$$1 \le i \le 2n$$$).

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

Выведите единственное число — среднее арифметическое целочисленных точек отрезков с абсолютной погрешностью не более $$$10^{-6}$$$.

Примеры
Входные данные
2
-3
-1
2
5
Выходные данные
1.1428571428571427937
Входные данные
3
-156
-25
-2
78
998
1003
Выходные данные
-13.082191780821917249
Примечание

В первом примере рассматриваются отрезки [$$$-3, -1$$$] и [$$$2, 5$$$]. Целые числа, входящие хотя бы в один из них: $$$-3, -2, -1, 2, 3, 4, 5$$$. Их среднее арифметическое: $$$\frac{-3 - 2 - 1 + 2 + 3 + 4 + 5}{7} = \frac{8}{7} \approx 1.14285714$$$. Тогда верными ответами будут считаться: $$$1.142857$$$; $$$1.1428571$$$; $$$1.142858$$$, а неверными: $$$1.142856$$$; $$$1.1428561$$$.