1239 - 植树节（planting）

植树节快要到了，学校要组织志愿者去给树苗浇水。有一排树苗，编号依次是 0,1,2, . . . 。现有 n 个志愿者去给树苗浇水，第 i 个志愿者选定了一个区间 [ $a_i,b_i$ ] ，表示第 i 个志愿者将 [ $a_i,b_i$ ] 这一区间内的每一棵树都浇一次水。如某个志愿者选择的浇水区间为 [4,9] ，表示他将给编号为 4,5,6,7,8,9 的树各浇水一次。当所有的志愿者完成各自所选区间的浇水后，可能有些树苗被不同的志愿者浇水多次，也可能有的树苗一次也没被浇过水。请你求出浇水最多的树苗被浇了多少次。

输入

第 1 行，一个整数 n ，表示志愿者的人数。

第 2 行到第 n + 1 行，每行两个整数 $a_i,b_i$ （ i= 0,1,2, . . . n − 1），表示志愿者 i 选择的浇水区间。

输出

输出 1 行， 1 个整数，表示浇水最多的树苗被浇水的次数。

样例

输入

输出

输入

4
1000000 1000000 
1000000 1000000 
0 1000000 
1 1000000

输出

提示

对于所有的数据： $n \leq 10^5$ ； $0 \leq a_i \leq b_i \leq 10^6$ 。

测试点编号	$a_i \leq$	$b_i \leq$	$n \leq$	特殊性质
1,2,3	$10^3$	$10^3$	$10^3$	无
4,5,6,7	$10^6$	$10^6$	$10^5$	无
8	$10^6$	$10^6$	$10^5$	$a_i=b_i$
9	$10^6$	$10^6$	$10^5$	$a_i=1,b_i=10^3$
10	$10^6$	$10^6$	$10^5$	无

来源

CSP-J2022

时间限制	1 秒
内存限制	128 MB

讨论统计

上一题下一题