Лента на трещинах

У школьной мастерской есть длинная прямая дорожка, и ребята заклеивают на ней трещины ремонтной лентой. За один выход они заклеивают один отрезок дорожки от точки l до точки r (в сантиметрах от начала дорожки). Отрезки могут перекрываться и даже полностью лежать внутри других.

Нужно понять, сколько сантиметров дорожки окажется заклеено хотя бы одним слоем ленты.

Важно: координаты могут быть большими (как на олимпиадах), результат тоже может не помещаться в 32-битный тип. В Python это не проблема, но в других языках нужен 64-битный тип.

Формат ввода

В первой строке целое число n — сколько раз выходили клеить ленту. Далее идут n строк, в каждой два целых числа l и r — границы отрезка.

Формат вывода

Выведите одно целое число — общую длину объединения всех отрезков.

Ограничения

• 2 ≤ n ≤ 140000
• -10^9 ≤ l ≤ r ≤ 10^9
• Ответ может быть больше 2^31 − 1 (используйте 64-битную арифметику).

Пример

Ввод:

4
1 5
2 3
7 10
4 8

Вывод:

9

Пояснение: объединение — это отрезок [1, 10], его длина 9.

Ключевое наблюдение: если упорядочить все отрезки по l, то объединение можно собрать одним проходом. Мы всегда держим «текущий склеенный» отрезок [cur_l, cur_r]. Следующий отрезок либо пересекается с ним (тогда объединение просто расширяется), либо начинается правее (тогда текущий кусок закончился, его длину можно добавить к ответу).

Почему работает: после сортировки никакой будущий отрезок не может начаться левее текущего, значит «дырка» между cur_r и новым l уже никогда не закроется — можно фиксировать длину.

План решения:

• Считать все пары (l, r).
• Отсортировать список по l (при равных l — по r тоже, стандартная сортировка кортежей).
• Инициализировать cur_l, cur_r первым отрезком, ans = 0.
• Для каждого (l, r) дальше:
• если l <= cur_r, отрезки соприкасаются/перекрываются, обновить cur_r = max(cur_r, r);
• иначе добавить длину текущего: ans += cur_r - cur_l, и начать новый: cur_l, cur_r = l, r.
• После цикла не забыть добавить последний кусок: ans += cur_r - cur_l.

Сложность: сортировка O(n log n), проход O(n), память O(n).

Частая ошибка: путать длину на прямой с количеством целых точек. Здесь длина отрезка — это r - l (как в примере: [1, 10] даёт 9). Ещё грабля: не склеивать «стыкующиеся» отрезки — условие для объединения должно быть l <= cur_r, а не строгое l < cur_r.