Magry的朋友很多 - Wonderland的邀请篇

题目描述

本来呢，Wonderland每周五晚上要带大家计组上机。可是这次，她要和jhljx带着他们的无人机去厦门参加比赛。这可怎么办？于是Wonderland找到了Magry，要Magry替她去一回，回头要给Magry一系列来自厦门的好吃的。

可是Magry很忙，不仅仅要给大家出算法题，还要上课写作业出助教版解题报告准备TOEFL考试blabla的……加上这件事的话无疑是雪上加霜。

不过Magry不能一心二用，只能在同一时间做一件事。

已知：

1. Magry要做的一系列事情总共有$N$件，每件事情开始时间为$S_{i}$，结束时间为$F_{i}$，表示活动的时间为半开半闭区间$[S_{i},F_{i})$；
2. Magry要求所有的任务不重叠，即对于任意不同的任务$i$与任务$j$，$[S_{i}, F_{i})$与$[S_{j},F_{j})$不重叠，需要注意的是$F_{i}=S_{j}$时不算做任务$i$与任务$j$重叠。

那么问题来了：Magry最多能完成的事情有多少件？

输入

多组输入数据（不超过5组）。

每组数据第一行为一个正整数$N$，代表任务数目，$1 \leq N \leq 100,000$

接下来$N$行，每行2个非负整数$S_{i}, F_{i}$，对于第$i$件任务，代表该任务的开始时间和结束时间。保证$0 \leq S_{i} < F_{i} \leq 1,000,000$

需要特别注意的是，对于分数为60%的数据，给出的任务不一定以任务结束时间排好序。

输出

对于每组数据，输出一行，一个数，Magry最多能完成的任务数目。

输入样例

3
1 2
2 3
0 4

输出样例

2