F. Монстры из пудинга
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В данной задаче речь пойдёт про упрощённую модель игры Pudding Monsters.

Важным этапом разработки любой игры является создание игровых карт. Поле для игры в Pudding Monsters представляет собой квадратную сетку n × n, в n клетках которой расположены монстры, а в некоторых остальных — игровые объекты. Игровая механика заключается в том, что игрок должен перемещать монстров по полю, при этом, оказавшись рядом, два маленьких монстра склеиваются в одного большого (они ведь из пудинга, вы же помните?).

Исследования показали, что самые интересные карты получаются, если исходно в каждой вертикали и каждой горизонтали расположено по монстру, а дальнейшая специфика карты уже задаётся правильной расстановкой остальных игровых объектов.

Частым приёмом для упрощения процесса разработки является переиспользование имеющихся ресурсов. Например, имея большую карту n × n, можно выделить из неё квадратную часть меньшего размера k × k, содержащую k монстров, и предложить в качестве упрощённой версии оригинальной карты.

Вас интересует, сколькими способами можно выделить из исходной карты квадратный фрагмент k × k (1 ≤ k ≤ n), содержащий ровно k монстров из пудинга. Определите это количество.

Входные данные

В первой строке следует единственное число n (1 ≤ n ≤ 3 × 105) — размер исходного поля.

В последующих n строках следуют координаты клеток, в которых исходно расположены монстры. i-я из последующих строк содержит два числа ri, ci (1 ≤ ri, ci ≤ n) — номер строки и номер столбца ячейки, в которой исходно находится i-й из монстров.

Гарантируется, что все ri — различные числа и все ci — различные числа.

Выходные данные

Выведите количество различных квадратных фрагментов исходного поля, которые можно выделить в качестве самостоятельной карты.

Примеры
Входные данные
5
1 1
4 3
3 2
2 4
5 5
Выходные данные
10