问题陈述
你被给予 N 片段 [L_1, R_1], [L_2, R_2], \ldots, [L_N, R_N] 。
一个子集 S 集合中的 \lbrace 1, 2, \ldots, N \rbrace 据说是 好套装 如果:
- 对于所有人 i, j \in S至少满足以下两个条件中的一个:
- 线段 [L_i, R_i] 包含线段 [L_j, R_j];
- 线段 [L_j, R_j] 包含线段 [L_i, R_i].
这里,线段 [L, R] 被认为包含另一个线段 [L', R'] 当且仅当 L \leq L' 和 R' \leq R.
找到一个好集合的最大可能大小。
约束
- 1 \leq N \leq 2 \times 10^5
- 0 \leq L_i < R_i \leq 10^9
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N L_1 R_1 L_2 R_2 \vdots L_N R_N
输出
打印答案。
示例输入 1
4 1 3 2 4 3 4 1 4
示例输出 1
3
该套 \lbrace 2, 3, 4 \rbrace 是具有最大大小的好集合。实际上,
- 为 2, 3 \in S, [L_2, R_2] 包含 [L_3, R_3];
- 为 2, 4 \in S, [L_4, R_4] 包含 [L_2, R_2];和
- 为 3, 4 \in S, [L_4, R_4] 包含 [L_3, R_3];
因此大小 3 。
示例输入 2
3 0 1 0 1 0 1
示例输出 2
3
示例输入 3
9 1 6 1 3 3 6 4 6 2 5 1 2 3 4 3 5 2 7
示例输出 3
4