题目描述

为了满足他所饲养的 N 头奶牛（$1 \le N \le 50,000$）日益增长的需求，农夫约翰购买了一台新的汽水机。他想找出安装这台机器的最佳位置。

奶牛们放牧的牧场可以表示为一条一维数轴。第 $i$ 头奶牛的活动范围为 $A_i \dots B_i$（包含两个端点），其中：

• $1 \le A_i \le B_i$
• $A_i, B_i \le 1,000,000,000$

农夫约翰可以将汽水机放置在 $1 \dots 1,000,000,000$ 范围内的任意一个整数位置。

由于奶牛们非常懒，想尽可能少地移动，因此每头奶牛都希望汽水机被安装在自己的活动范围内。

然而，遗憾的是，并不总能满足所有奶牛的愿望。因此，农夫约翰想知道：最多能满足多少头奶牛？

例如，假设有 4 头奶牛，它们的活动范围分别为：

• $3 \dots 5$
• $4 \dots 8$
• $1 \dots 2$
• $5 \dots 10$

它们的活动范围如下图所示：

         1   2   3   4   5   6   7   8   9  10  11  12  13
         |---|---|---|---|---|---|---|---|---|---|---|---|-...
                 aaaaaaaaa
                     bbbbbbbbbbbbbbbbb
         ccccc           ddddddddddddddddddddd

可以看到，第 1、2、4 头奶牛的活动范围都包含位置 $5$，而第 3 头奶牛的活动范围与它们没有交集。

因此，最多可以满足 3 头奶牛。

输入格式

• 第一行：一个整数 $N$。
• 接下来 $N$ 行：第 $i+1$ 行包含两个用空格分隔的整数 $A_i$ 和 $B_i$，表示第 $i$ 头奶牛的活动范围。

输出格式

输出一行，一个整数，表示活动范围包含同一个位置的奶牛数量的最大值。

4 
3 5 
4 8 
1 2 
5 10 

3 

提示

如果将汽水机放置在位置 $5$，那么第 $1$、$2$、$4$ 头奶牛都可以得到满足。

不可能同时满足全部 $4$ 头奶牛。