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

Вам задано $$$n$$$ отрезков $$$[l_1, r_1], [l_2, r_2], \dots, [l_n, r_n]$$$. Каждый отрезок одного из двух цветов: $$$i$$$-й отрезок покрашен в цвет $$$t_i$$$.

Назовем пару отрезков $$$i$$$ и $$$j$$$ плохой, если выполняются два условия:

  • $$$t_i \ne t_j$$$;
  • отрезки $$$[l_i, r_i]$$$ и $$$[l_j, r_j]$$$ пересекаются, касаются или вкладываются, т. е. существует целое число $$$x$$$, такое, что $$$x \in [l_i, r_i]$$$ и $$$x \in [l_j, r_j]$$$.

Определите, какое максимальное количество отрезков из заданных можно выбрать так, чтобы среди выбранных не было ни одной плохой пары.

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

В первой строке задано единственное целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — количество отрезков.

В последующих $$$n$$$ строках задано по три целых числа $$$l_i, r_i, t_i$$$ ($$$1 \le l_i \le r_i \le 10^9; t_i \in \{1, 2\}$$$) — описание $$$i$$$-го отрезка.

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

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

Примеры
Входные данные
3
1 3 1
4 6 2
2 5 1
Выходные данные
2
Входные данные
5
5 8 1
1 3 2
3 4 2
6 6 1
2 10 2
Выходные данные
4
Входные данные
7
19 20 1
13 15 2
6 11 2
4 10 1
14 17 1
13 13 2
5 9 1
Выходные данные
5