Вам задано \(n\) отрезков \([l_1, r_1], [l_2, r_2], \dots, [l_n, r_n]\). Каждый отрезок одного из двух цветов: \(i\)-й отрезок покрашен в цвет \(t_i\).
Назовем пару отрезков \(i\) и \(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
2000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач