题目描述

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

有一排树苗，编号依次是 $0,1,2,\dots$。

现有 $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$ 选择的浇水区间。

输出格式

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

数据范围

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

样例

输入样例 1

4
2 5
1 4
3 3
7 9

输出样例 1

3

提示

样例中树 $3$ 被前三个志愿者都浇过，共 $3$ 次（树 $7,8,9$ 只被浇 $1$ 次）。

做法：区间加用差分数组，最后前缀和还原并取最大值。