题目描述

哦，那些挑剔的 $\red{N (1 <= N <= 50,000) }$头奶牛！他们非常挑剔，每个人只能在某个精确的时间间隔 $\red{A..B (1 <= A <= B <= 1,000,000) }$内挤奶，其中包括时间 $\red{A }$和 $\red{B}$。

显然，$\red{FJ }$必须创建一个预订系统来确定每头奶牛的挤奶时间可以分配到哪个摊位。当然，没有一头奶牛会与其他奶牛分享如此私密的时刻。

帮助 $\red{FJ }$确定：

$\red{* }$牛舍中所需的最少栏位数量，以便每头奶牛可以有自己的挤奶时间

$\red{* }$随着时间的推移将奶牛分配到这些栏位 有$\red{N}$头牛,每头牛有个喝水时间,这段时间它将专用一个$\red{Stall }$现在给出每头牛的喝水时间段,问至少要多少个$\red{Stall}$才能满足它们的要求

输入格式

第 $\red{1 }$行：单个整数 $\red{N *}$

第 $\red{2..N+1 }$行：第 $\red{i+1 }$行用两个空格分隔的整数描述奶牛 $\red{i }$的挤奶间隔。

输出格式

第 $\red{1 }$行：谷仓必须拥有的最小摊位数。

第 $\red{2..N+1 }$行：第 $\red{i+1 }$行描述了奶牛 $\red{i }$在挤奶期间将分配到的摊位。

样例

输入样例

5
1 10
2 4
3 6
5 8
4 7

输出样例

4

提示

输出详细信息：以下是此输出的图形时间表：

Time     1  2  3  4  5  6  7  8  9 10
Stall 1 c1>>>>>>>>>>>>>>>>>>>>>>>>>>>
Stall 2 .. c2>>>>>> c4>>>>>>>>> .. ..
Stall 3 .. .. c3>>>>>>>>> .. .. .. ..
Stall 4 .. .. .. c5>>>>>>>>> .. .. ..

其他输出可能使用相同数量的暂停

不妨试下这个数据,对于按结束点$\red{SORT,}$再$\red{GREEDY}$的做法 $\red{1 3 5 7 6 9 10 11 8 12 4 13 }$正确的输出应该是$\red{3}$