Дистанционный практикум по программированию

Определение. Интервал прямой с целочисленными координатами [a, b) содержит левую границу – точку a и не содержит правую границу – точку b.

Интервал от 0 до 10⁹ выкрасили в белый цвет. Затем было выполнено N операций перекрашивания. При каждой операции цвета в интервале, границы которого задаются, меняются на противоположный (белый на черный, черный на белый).

Требуется написать программу, которая найдет самый длинный интервал белого цвета после заданной последовательности операций перекрашивания.

Исходные данные

Входные данные содержат в первой строке число N (1 <= N <= 500000) и затем N строк с границами интервалов (числа в диапазоне от 0 до 10⁹).

Результат

Выведите одно число – длину самого большого белого интервала.

Пример

4
20 50
10 35
40 90
100 1000000000

15