28613번 - Финальное противостояние 다국어

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

Сам город можно представить в виде бесконечной координатной прямой. Боты нападают последовательными волнами, каждая из $n$ волн представляет собой отрезок этой прямой, который целиком заполнен ботами. Нео знает, что в $i$-ю волну боты будут занимать отрезок с концами в точках $l_i$ и $r_i$ (то есть $[l_i, r_i]$).

Тринити считает группу последовательных волн с $a$-й по $b$-ю включительно опасной, если при пересечение занятых ботами в эти волны отрезков имеет длину не меньше $m_1$ и не больше $m_2$. Иными словами, пара чисел $(a, b)$, для которых $a \leqslant b$, задает опасную группу волн тогда и только тогда, когда $$m_1 \leqslant \left|\bigcap\limits_{a \leqslant i \leqslant b} [l_i, r_i] \right| \leqslant m_2\text{.}$$

Например, если $n = 3$ и $[l_1, r_1] = [4, 7]$, $[l_2, r_2] = [5, 8]$ и $[l_3, r_3] = [3, 6]$, то пересечение отрезков первых двух волн равно $[4, 7] \cap [5, 8] = [5, 7]$ и имеет длину $2$, а пересечение всех трех отрезков равно $[5, 6]$ и имеет длину $1$. При $m_1 = 2$, первые две волны вместе будут опасными, а все три вместе --- нет. Обратите внимание, что если какая-то группа волн является опасной, это не значит, что любая содержащая ее группа волн также опасна.

Помогите Нео и Тринити найти количество опасных групп волн, чтобы они могли поскорее выбрать план действий.

В первой строке ввода через пробел даны три целых числа $n$, $m_1$ и $m_2$ --- количество волн и границы допустимых значений длины пересечения отрезков ($1 \leqslant n \leqslant 2 \cdot 10^5$; $0 \leqslant m_1 \leqslant m_2 \leqslant 10^9$).

В следующих $n$ строках перечислены координаты концов отрезков, заполненных ботами: в $i$-й строке через пробел даны целые числа $l_i$ и $r_i$ --- границы $i$-го отрезка ($0 \leqslant l_i < r_i \leqslant 10^9$).

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

В первом примере в качестве опасной группы подойдет любая группа, содержащая четвертую волну, так как ее длина равна $1$ и ее отрезок содержится во всех остальных отрезках, а значит и пересечение будет иметь длину $1$. А также, помимо этого, подойдет группа из первых трех волн, имеющая пересечение отрезков, равное $[2, 4]$.

Во втором примере подойдет любая группа, содержащая третью или четвертую волну. Несложно заметить, что группы, состоящие только из двух первых или двух последних волн, имеют пересечение отрезков длины хотя бы $2$. Всего таких подходящих групп ровно $15$.