You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

给你 N 个区间，编号从 1 到 N。区间 i 是 $[L_i, R_i]$。 两个区间 $[l_a, r_a]$ 和 $[l_b, r_b]$ 被认为相交当且仅当满足以下条件之一：$(l_a < l_b < r_a < r_b)$ 或 $(l_b < l_a < r_b < r_a)$。 定义 $f(l, r)$ 为与区间 $[l, r]$ 相交的区间 $i (1 ≤ i ≤ N)$ 的数量。 在所有满足 $0 ≤ l < r ≤ 10^9$ 的整数对 $(l, r)$ 中，找到使 $f(l, r)$ 最大的 $(l, r)$。如果有多个这样的对，选择 $l$ 最小的对。如果仍然有多个对，选择 $r$ 最小的对。（由于 $0 ≤ l < r$，所以 $(l, r)$ 的答案是唯一确定的。）

输入格式

输入从标准输入给出，格式如下： N L_1 R_1 L_2 R_2 ... L_N R_N

输出格式

以以下格式打印所求的对 (l, r)： l r

5
1 7
3 9
7 18
18 14
21 20

4 11

$f(l, r)$ 的最大值是 4，且在 $f(l, r)$ = 4 的对中，l 最小的是 4。满足 $f(l, r)$ = 4 且 $l = 4$ 的对如下：

(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
856077192 996441446
292515177 935800360
395653286 68844528
718669087 92156831
325371222 425399117
375628174 907494598
835882153 99394341
148179224 887672320
379807808 91157526
93538028 188312295
249811118 77598537

396653287 887672321

约束条件

$1 ≤ N ≤ 10^5$ $0 ≤ L_i ≤ R_i ≤ 10^9 (1 ≤ i ≤ N)$ 所有输入值都是整数。