区间选点

题目描述

给定 N 个闭区间 ([a_i, b_i])，请你在数轴上选择尽可能少的点，使得每个区间内至少包含一个选出的点（包括端点）。

输出所需点的最小数量。

输入

• 第一行包含一个整数 N （ 1 \le N \le 10^5 ），表示区间的个数。
• 接下来 N 行，每行包含两个整数 a_i 和 b_i （ -10^9 \le a_i \le b_i \le 10^9 ），表示第 i 个区间的左右端点。

输出

输出一个整数，表示所需的最少点数。

样例

提示

数据范围与约定

• 1 \le N \le 10^5
• -10^9 \le a_i \le b_i \le 10^9