103605: [Atcoder]ABC360 F - InterSections

Problem Statement

You are given $N$ intervals numbered $1$ to $N$. Interval $i$ is $[L_i, R_i]$.

Two intervals $[l_a, r_a]$ and $[l_b, r_b]$ are said to intersect if and only if they satisfy either $(l_a < l_b < r_a < r_b)$ or $(l_b < l_a < r_b < r_a)$.

Define $f(l, r)$ as the number of intervals $i$ ($1 \leq i \leq N$) that intersect with the interval $[l, r]$.

Among all pairs of integers $(l, r)$ satisfying $0 \leq l < r \leq 10^{9}$, find the pair $(l, r)$ that maximizes $f(l, r)$. If there are multiple such pairs, choose the one with the smallest $l$. If there are still multiple pairs, choose the one with the smallest $r$ among them. (Since $0 \leq l < r$, the pair $(l, r)$ to be answered is uniquely determined.)

Constraints

• $1 \leq N \leq 10^{5}$
• $0 \leq L_i < R_i \leq 10^{9}$ $(1 \leq i \leq N)$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

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

Output

Print the sought pair $(l, r)$ in the following format:

$l$ $r$

Sample Input 1

5
1 7
3 9
7 18
10 14
15 20

Sample Output 1

4 11

The maximum value of $f(l, r)$ is $4$, and among the pairs $(l, r)$ that achieve $f(l, r) = 4$, the smallest $l$ is $4$. The pairs $(l, r)$ that satisfy $f(l, r) = 4$ and $l = 4$ are the following three:

• $(l, r) = (4, 11)$
• $(l, r) = (4, 12)$
• $(l, r) = (4, 13)$

Among these, the smallest $r$ is $11$, so print $4$ and $11$.

Sample Input 2

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

Sample Output 2

396653207 887672321

问题陈述

给你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)是唯一确定的。）

约束条件

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

输入

输入从标准输入以以下格式给出：

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

输出

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

$l$ $r$

示例输入1

5
1 7
3 9
7 18
10 14
15 20

示例输出1

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)

在这些中，最小的r为11，所以打印4和11。

示例输入2

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

示例输出2

396653207 887672321