EduBrick

Вложенные отрезки

2000 мс · 256 МБ · всё или ничего

Даны nn отрезков на прямой; все 2n2n концов различны. Посчитайте количество пар отрезков, один из которых целиком лежит внутри другого.

Отрезок jj вложен в отрезок ii, когда li<ljl_i < l_j и rj<rir_j < r_i. Два условия сразу — значит одно из них надо «снять» порядком обработки.

Формат ввода

В первой строке nn (1≤n≤2⋅1051 \le n \le 2 \cdot 10^5). В каждой из следующих nn строк — два числа lil_i и rir_i (1≤li<ri≤2n1 \le l_i < r_i \le 2n). Все 2n2n чисел попарно различны.

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

Выведите количество пар вложенных отрезков.

Примеры

ввод
1
1 2
вывод
0
Разбор идеи от автора задачи. Сначала попробуйте сами.
Войдите, чтобы отправлять решения.