Ленивые лесорубы

시간 제한2초메모리 제한1024 MB

요약

각 목수가 벽 높이를 반 미터씩 깎는 구간이 주어질 때, 연속한 목수 구간 [a, b]를 골라 모든 지점의 높이 변화가 정수 미터가 되는 경우의 수를 센다.

난이도: 보통10점 중 7점
유형: 누적 합, 해시맵, 배열, 비트 연산
정답자: 아직 제출이 없습니다

문제

Малефисента воздвигла терновую стену вокруг Топких Болот. И теперь король Стефан хочет разрушить её. Для этого, он планирует нанять лесорубов, которые будут рубить эту стену.

Стена имеет огромную высоту и бесконечно простирается вдоль прямой. Введём на ней числовую ось. Всего есть $n$ лесорубов, пронумерованных от $1$ до $n$ . Лесорубы очень ленивые, и рубят стену лишь для того, чтобы заработать. Поэтому, если нанять $i$ -го лесоруба, он уменьшит высоту стены на отрезке от координаты $l\_i$ до координаты $r\_i$ лишь на полметра. И при этом, каждый лесоруб может быть нанят не более одного раза.

Стефан понял, что он не сможет прорубить стену. Однако, ему стало интересно, сколькими способами он может выбрать два целых числа $a$ и $b$ ( $1 \le a \le b \le n$ ), что если нанять всех лесорубов с номерами от $a$ до $b$ и только их, высота стены всюду изменится на целое число метров. Обратите внимание, что нулевое изменение высоты также считается изменением на целое число метров.

입력

В первой строке дано одно целое число $n$ --- количество лесорубов ( $1 \le n \le 200\\,000$ ).

В следующих $n$ строках даны по два целых числа $l\_i$ и $r\_i$ --- координаты начала и конца отрезка стены, который уменьшит $i$ -й лесоруб ( $-10^9 \le l\_i < r\_i \le 10^9$ ).

출력

В единственной строке выведите ответ на задачу.

예제2

예제 1
입력
```
4
1 3
2 3
2 3
1 3
```
예상 출력
```
2
```
예제 2
입력
```
3
1 2
2 3
1 3
```
예상 출력
```
1
```