Задача B. Парные максимумы

Автор:Артём Завгороднев   Ограничение времени:3 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  

Условие

Вам дано n одномерных отрезков ненулевой длины(каждый отрезок представляется двумя целыми числами — координатами его концов).

Давайте определим функцию f(x) как количество отрезков, покрывающих точку x (отрезок покрывает точку x, если lxr где l — левый конец отрезка, а r — правый).

Пару точек x1 и x2 назовём парным максимумом, если они по отдельности принадлежат большему числу отрезков, чем любая другая точка. Другими словами, если для любого x отличного от x1 и x2 выполняется f(x) < f(x1) и f(x) < f(x2).

Ваша задача определить, сколько существует пар целочисленных точек, которые могут стать парными максимумами, если удалить несколько (возможно ни одного) отрезков.

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

Первая строка каждого набора содержит целое число n.

Далее следует n строк, i-я содержит два целых числа li, ri - концы отрезков.

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

Вам необходимо вывести одно целое число - количество парных пар целочисленных точек, которые могут стать парными максимумами.

Ограничения

1 ≤ n ≤ 2 * 105

0 ≤ li,ri ≤ 1018, li < ri

Примеры тестов

Стандартный вход Стандартный выход
1
5
3 5
3 6
5 6
5 9
6 9
1
2
4
1 5
5 10
10 15
15 20
2

0.083s 0.012s 15