题目描述

给定 $N$ 个闭区间 $[l_i, r_i]$，请在数轴上选择尽量少的点，使得每个区间内至少包含一个选出的点。输出选择的点的最少数量。

输入格式

第一行一个整数 $N$（$1 \le N \le 100000$），表示闭区间的个数。

接下来 $N$ 行，每行两个整数 $l_i, r_i$（$-100000 \le l_i \le r_i \le 100000$），表示一个闭区间。

输出格式

一行，一个整数，表示最少需要选择的点的数量。

样例

5
0 3
1 2
-1 2
0 1
4 5

2

说明/提示

两个区间不重叠时需要两个点；有重叠时只需一个点。将所有区间按右端点升序排序，依次扫描：若当前区间的左端点大于已选重叠区间的右端点，说明出现了一个新的重叠区间，需要多一个点。重叠区间的数量就是所选点的数量。