#P3478. 迎江寺

迎江寺

题目描述

刚迎来了2014年元旦,又将逢春节,每次大年初一小明都要和爸爸妈妈到迎江寺去烧香拜佛,祝愿新的一年里心想事成。

记得每年都人山人海,非常热闹。进进出出的人实在太多了,寺里的住持想知道,在某一时刻,寺里的游客的最多人数,以便来年改进措施解决人满为患的状况,如超过一定人数,就要实行限流。大年初一共有 nn 位游客入寺,第 ii 位游客入寺时间为 aia_i,在 bib_i 时刻离开寺庙。因此第 ii 位游客在寺内的时间是 [ai,bi][a_i, b_i],即满足 aitbia_i \le t \le b_i 的所有时刻 tt。请写个程序,读入 aia_ibib_i1in1 \le i \le n),找出同一时刻最多会有多少游客在寺中。

住持想知道最多有多少游客在同一时刻都在寺内,但游客们进进出出寺庙的记载实在很乱,于是住持请聪明的你编程帮忙统计。

输入格式

第一行一个整数 nn,表示共有 nn 个游客进出寺庙的记载。
接下来 nn 行,每行两个整数 aabb,表示有一个游客在第 aa 时刻进入寺庙,在第 bb 时刻后离开寺庙。

输出格式

一行一个整数,表示最多有多少游客在同一时刻都在寺庙里面。

样例

4
2 6
8 9
1 5
1 2
3

样例解释
第一个游客在时刻 22 进入,时刻 66 后离开;第二个游客在时刻 88 进入,时刻 99 后离开;第三个游客在时刻 11 进入,时刻 55 后离开;第四个游客在时刻 11 进入,时刻 22 后离开。在时刻 22 时,第一个、第三个和第四个游客都在寺庙内,共 33 人,为最大人数。

数据范围

  • 对于 50%50\% 的数据:1n10001 \le n \le 10001ab30001 \le a \le b \le 3000
  • 对于 100%100\% 的数据:1n1000001 \le n \le 1000001ab1081 \le a \le b \le 10^8