区间相交

题目描述

给定编号 $1$ 到 $N$ 的 $N$ 个区间。区间 $i$ 为 $[L_i, R_i]$。

当且仅当两个区间 $[l_a, r_a]$ 和 $[l_b, r_b]$ 满足 $(l_a \lt l_b \lt r_a \lt r_b)$ 或 $(l_b \lt l_a \lt r_b \lt r_a)$ 时,称它们相交。

定义 $f(l, r)$ 为与区间 $[l, r]$ 相交的区间 $i$ $(1 \le i \le N)$ 的个数。

在所有满足 $0 \le l \lt r \le 10^{9}$ 的整数对 $(l, r)$ 中,求使 $f(l, r)$ 最大的对 $(l, r)$。若有多个这样的对,选择 $l$ 最小的;若仍有多个,选择其中 $r$ 最小的。(由于 $0 \le l \lt r$,要输出的对 $(l, r)$ 是唯一确定的。)

输入格式

输入按以下格式从标准输入给出:

$N$
$L_1$ $R_1$
$L_2$ $R_2$
$\vdots$
$L_N$ $R_N$

输出格式

按以下格式输出所求的 $(l, r)$:

$l$ $r$

样例

5
1 7
3 9
7 18
10 14
15 20

4 11

$f(l, r)$ 的最大值为 4,在达到 $f(l, r) = 4$ 的对 $(l, r)$ 中,最小的 $l$ 是 4。满足 $f(l, r) = 4$ 且 $l = 4$ 的对 $(l, r)$ 有以下五个:

$(l, r) = (4, 11)$

$(l, r) = (4, 12)$

$(l, r) = (4, 13)$

$(l, r) = (4, 16)$

$(l, r) = (4, 17)$

其中 $r$ 最小的是 11,因此输出 4 和 11。

11
856977192 996441446
298251737 935869360
396653206 658841528
710569907 929136831
325371222 425309117
379628374 697340458
835681913 939343451
140179224 887672320
375607390 611397526
93530028 581033295
249611310 775998537

396653207 887672321

数据范围

• $1 \le N \le 10^{5}$
• $0 \le L_i \lt R_i \le 10^{9}$ $(1 \le i \le N)$
• 所有输入值均为整数。