Вам задано \(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]\).
Определите, какое максимальное количество отрезков из заданных можно выбрать так, чтобы среди выбранных не было ни одной плохой пары.
Выходные данные
Выведите максимальное количество отрезков, которые можно выбрать так, чтобы среди выбранных отрезков не было ни одной плохой пары.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
1 3 1
4 6 2
2 5 1
|
2
|
|
2
|
5
5 8 1
1 3 2
3 4 2
6 6 1
2 10 2
|
4
|
|
3
|
7
19 20 1
13 15 2
6 11 2
4 10 1
14 17 1
13 13 2
5 9 1
|
5
|