问题描述

假设有一个活动集合，每个活动都有一个开始时间和结束时间。你需要从这些活动中选择一些活动来参加，使得这些活动的时间不会相互冲突（即任意两个活动的时间区间没有交集），并且选择的活动数量尽可能多。

具体来说，输入会给出一系列活动的开始时间和结束时间，你需要输出最多能选择的活动数量。

格式

输入

第一行活动场次 第二行到最后输出各个活动安排时间

输出

输出最多安排几场

样例

3
1 3
2 4
3 5

2

样例2

4
1 2
2 3
3 4
4 5

4

提示

解释1: 可以选择活动 (1, 3) 和 (3, 5)，这两个活动时间不冲突，所以最多能选择 2 个活动。

解释2: 所有活动的时间都不冲突，可以全部选择，所以最多能选择 4 个活动。