80202205 - 2023补赛_A_planting

时间限制

1000 毫秒

内存限制

128 MB

通过次数

3

提交次数

10

植树节快要到了,学校要组织志愿者去给树苗浇水。

有一排树苗,编号依次是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选择的浇水区间。

对于100%的数据:

n \le 10^5

0 \le a_i \le b_i \le 10^6

输出

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

样例

输入

4
0 2
2 4
1 4
6 7

输出

3

输入

4
1000000 1000000
1000000 1000000
0 1000000
1 1000000

输出

4