I - InterSections Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 550 点

問題文

1 から N までの番号のついた 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) を 1 \leq i \leq N を満たし、区間 [l,r] と区間 i が交差する i の個数と定義します。

0 \leq l < r \leq 10^{9} を満たす整数の組 (l,r) において、 f(l,r) の最大値を達成する (l,r) の組のうち l が最小のものを答えてください。そのような組が複数存在する場合はさらにそのうちで r が最小のものを答えてください (0 \leq l < r より、 答えるべき (l,r) の組は一意に定まります)。

制約

  • 1 \leq N \leq 10^{5}
  • 0 \leq L_i < R_i \leq 10^{9} (1 \leq i \leq 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) は以下の 5 通りです。

  • (l,r)=(4,11)
  • (l,r)=(4,12)
  • (l,r)=(4,13)
  • (l,r)=(4,16)
  • (l,r)=(4,17)

このうち、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

Score : 550 points

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 five:

  • (l, r) = (4, 11)
  • (l, r) = (4, 12)
  • (l, r) = (4, 13)
  • (l, r) = (4, 16)
  • (l, r) = (4, 17)

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