Требуется найти число способов выбрать из набора интервалов максимальное множество непресекающихся интревалов

[Filia]

Условие:
Задано N интервалов (a_i, b_i) , a_i < b_i, на прямой.

Числа a_i и b_i целые и не превосходят по модудю 2'000'000'000.

Требуется найти число способов выбрать из них максимальное множество непресекающихся интревалов. Интервалы могут совпадать, но при этом они считаются разными (интервалы — это бозоны, а не фермионы).

Вход В первой строке N (1 ≤ N ≤ 100000) Cледующие N строк содержат координаты концов интервалов. В каждой строке записано два числа a_i и b_i, разделённых пробелом.

Выход Нужно вывести единственное число — искомое число способов. Известно, что это оно не превосходит 10^18