您将获得 $$$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]$$$ 相交、嵌入或接触,i。 e.存在一个整数$$$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$$$ 段的描述。
输出
打印可以选择的最大段数,以便所选段之间不存在坏对。
示例
输入 #1
3 1 3 1 4 6 2 2 5 1
输出 #1
2
输入 #2
5 5 8 1 1 3 2 3 4 2 6 6 1 2 10 2
输出 #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
输出 #3
5