На числовой прямой нарисованы \(n\) отрезков. Отрезки могут
пересекаться, накладываться или совпадать. Точка прямой считается закрашенной,
если она принадлежит хотя бы одному отрезку.
Найдите суммарную длину закрашенной части прямой.
Формат входных данных
В первой строке — целое число \(n\)
(\(1 \le n \le 10^5\)).
В каждой из следующих \(n\) строк — два целых числа
\(l_i\) и \(r_i\)
(\(-10^9 \le l_i \le r_i \le 10^9\)) — концы очередного отрезка.
Формат выходных данных
Одно целое число — длина объединения всех данных отрезков.
Примечание
В первом примере отрезки \([1, 5]\) и \([3, 7]\)
сливаются в один отрезок \([1, 7]\) длины \(6\).
Отдельный отрезок \([10, 12]\) добавляет ещё \(2\).
Итого: \(8\).
Во втором примере четыре отрезка стыкуются концом-к-началу и образуют один сплошной
отрезок \([0, 4]\) длины \(4\).
| № | Входные данные | Выходные данные |
|
1
|
3
1 5
3 7
10 12
|
8
|
|
2
|
4
0 1
1 2
2 3
3 4
|
4
|