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