На числовой прямой даны \(n\) отрезков. Для каждой
неупорядоченной пары отрезков \((i, j)\) рассмотрим длину
их пересечения. Если отрезки не пересекаются — длина пересечения равна нулю.
Найдите сумму длин пересечений по всем парам.
Формат входных данных
В первой строке — целое число \(n\)
(\(1 \le n \le 10^5\)).
В каждой из следующих \(n\) строк — два целых числа
\(l_i\) и \(r_i\)
(\(-10^9 \le l_i \le r_i \le 10^9\)) — концы очередного отрезка.
Формат выходных данных
Одно целое число — сумма длин пересечений по всем неупорядоченным парам отрезков.
Ответ может не помещаться в 32-битный тип.
Примечание
В первом примере три отрезка: \([0, 10]\),
\([2, 6]\), \([8, 15]\).
- Пересечение первого и второго — \([2, 6]\) длины \(4\).
- Пересечение первого и третьего — \([8, 10]\) длины \(2\).
- Пересечение второго и третьего пусто.
Сумма: \(4 + 2 + 0 = 6\).
Во втором примере четыре одинаковых отрезка длины \(10\).
Каждая из \(\binom{4}{2} = 6\) пар даёт пересечение длины
\(10\), итого \(60\).
| № | Входные данные | Выходные данные |
|
1
|
3
0 10
2 6
8 15
|
6
|
|
2
|
4
0 10
0 10
0 10
0 10
|
60
|