问题 K: 植树节

问题 K: 植树节

时间限制: 1 Sec  内存限制: 256 MB
提交: 189  解决: 90
[提交][状态][讨论版][命题人:]

题目描述

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

输入

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

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

输出

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

样例输入

样例输入1
4
0 2
2 4
1 4
6 7
样例输入2
4
1000000 1000000
1000000 1000000
0 1000000
1 1000000

样例输出

样例输出1
3
样例输出2
4

提示


对于所有的数据：n≤ 10^5；0 ≤ ai≤ bi ≤ 10^6 。



测试点编号  ai ≤      bi ≤     n ≤          特殊性质



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    ai==bi



9                10^6       10^6     10^5    ai=1 bi=10^3



10            10^6          10^6    10^5     无

[提交][状态]