该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

有若干个活动，第 $i$ 个开始时间和结束时间是 $[Si,fi)$ ，同一个教室安排的活动之间不能交叠，求要安排所有活动，最少需要几个教室？

Input Format

第一行一个正整数 $n$ 代表活动的个数。 之后 $n$ 行每行两个数 $s,t$ ，分别为开始/结束时间。 其中 $n\le 10000$ ， $0\le t1 < t2 < 1e9$ 。

Output Format

一行包含一个整数表示最少教室的个数。

3
1 2
3 4
2 9

2