← 返回题目列表

Codeforces · 1424/G

G. 年

中文机器翻译题面 查看原题

在其中一次太空任务中,人类在其中一颗行星上发现了以前生命存在的证据。他们很幸运地找到了一本书,上面写着这个星球上每个人的出生和死亡年份。有趣的是,这些年份的范围是 $$$(1, 10^9)$$$!因此,这颗行星被命名为Longlifer。

为了更多地了解长寿者以前的种群,科学家需要确定存活个体数量最多的年份,以及该年存活个体的数量。你的任务就是帮助科学家解决这个问题!

输入

第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^5$$$) — 人数。

以下 $$$n$$$ 行中的每一行都包含两个整数 $$$b$$$ 和 $$$d$$$ ($$$1 \le b \lt d \le 10^9$$$) 分别代表每个人的出生年份和死亡年份。

输出

打印两个由空白字符分隔的整数,$$$y$$$ — 存活人数最多的年份,$$$k$$$ — $$$y$$$ 年的存活人数。

如果有多个可能的解决方案,请打印年份最小的解决方案。

示例

输入 #1

3
1 5
2 4
5 6

输出 #1

2 2

输入 #2

4
3 4
4 5
4 6
8 10

输出 #2

4 2

注意

您可以假设一个从 $$$b$$$ 到 $$$d$$$ 的个体出生于 $$$b$$$ 年初,死亡于 $$$d$$$ 年初,因此生活了 $$$d$$$ - $$$b$$$ 年。