Рятувальники (Срібло)#10420
Фермер Джон відкрив для своїх корів плавальний басейн, сподіваючись, що це допоможе їм розслабитися і давати більше молока.
Для забезпечення безпеки він наймає корів рятувальниками, кожна з яких має зміну, що покриває неперервний проміжок часу протягом дня. Для простоти вважатимемо, що басейн відкритий щодня з моменту часу t = 0 до моменту часу t = 10^9, тому кожну зміну можна описати двома цілими числами: моментами часу, в які корова починає і закінчує свою зміну. Наприклад, рятувальник, що починає роботу в момент часу t = 4 і закінчує в момент часу t = 7, покриває три одиниці часу (зверніть увагу, що кінці проміжку є "точками" у часі).
На жаль, Фермер Джон найняв на одного рятувальника більше, ніж може собі дозволити. Враховуючи, що він повинен звільнити рівно одного рятувальника, яку найбільшу кількість часу можуть покрити зміни рятувальників, що залишилися? Проміжок часу вважається покритим, якщо на чергуванні перебуває хоча б один рятувальник.
Перший рядок містить ціле число n~(1 \le n \le 10^5). Кожен з наступних рядків описує рятувальника двома цілими числами в діапазоні від до 10^9: моментами початку і закінчення зміни цього рятувальника. Усі ці моменти часу різні. Зміни різних рятувальників можуть перетинатися.
Виведіть одне ціле число: найбільшу кількість часу, яку можна покрити, якщо Фермер Джон звільнить одного рятувальника.
Приклад 1