You are given $$$n$$$ segments $$$[l_1, r_1], [l_2, r_2], \dots, [l_n, r_n]$$$. Each segment has one of two colors: the $$$i$$$-th segment's color is $$$t_i$$$.
Let's call a pair of segments $$$i$$$ and $$$j$$$ bad if the following two conditions are met:
Calculate the maximum number of segments that can be selected from the given ones, so that there is no bad pair among the selected ones.
The first line contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — number of segments.
The next $$$n$$$ lines contains three integers $$$l_i, r_i, t_i$$$ ($$$1 \le l_i \le r_i \le 10^9; t_i \in \{1, 2\}$$$) — description of the $$$i$$$-th segment.
Print the maximum number of segments that can be selected, so that there is no bad pair among the selected segments.
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
Name |
---|