문제

K理事長は縦$N$行，横$N$列のマス目で表される模様を作ろうとしている．そのために，各マスに整数の番号で表される色を塗ることにした．以降，上から$i$行目($1 \le i \le N$)，左から$j$列目($1 \le j \le N$)のマスをマス$(i, j)$と呼ぶことにする．

現時点で，1列目と1行目のマスには既に色が塗られている．具体的には，マス$(i, 1)$ ($1 \le i \le N$) は色$A_i$で，マス$(1, j)$ ($1 \le j \le N$) は色$B_j$で塗られている．ここで$A_1 = B_1$である．

残りのマスについて，K理事長は以下の手順で色を塗っていく．

• $i = 2, 3, \ldots, N$の順に，以下の手順で$i$行目のマスに色を塗る．

  • $j = 2, 3, \ldots, N$の順に，マス$(i, j)$を

    • マス$(i-1, j)$に塗られている色
    • マス$(i, j-1)$に塗られている色

    のうち番号が大きい方の色で塗る．番号が同じ場合は，その色で塗る．

K理事長は，最終的に$N^2$個のマスすべてに色が塗られたとき，最も多くのマスに塗られた色の番号，およびその色が塗られているマスの個数を求めたい．

マス目の大きさおよび1列目と1行目のマスの情報が与えられたとき，最も多くのマスに塗られた色の番号とその色が塗られているマスの個数を求めるプログラムを作成せよ．最も多くのマスに塗られた色の番号が複数存在する場合，そのうち最も番号の大きいものを求め出力すること．

입력

入力は以下の形式で標準入力から与えられる．

$N$
$A_1$ $A_2$ $\cdots$ $A_N$
$B_1$ $B_2$ $\cdots$ $B_N$

출력

標準出力に，最も多くのマスに塗られた色の番号と，その色が塗られているマスの個数を空白区切りで1行に出力せよ．最も多くのマスに塗られた色の番号が複数存在する場合，そのうち最も番号の大きいものを出力すること．

제한

• $2 \le N \le 200\,000$．
• $1 \le A_i \le 10^9$ ($1 \le i \le N$)．
• $1 \le B_j \le 10^9$ ($1 \le j \le N$)．
• $A_1 = B_1$．
• 入力される値はすべて整数である．

서브태스크

1. (15点) $N \le 500$，$A_i \le 100\,000$ ($1 \le i \le N$)，$B_j \le 100\,000$ ($1 \le j \le N$)．
2. (10点) $N \le 500$．
3. (20点) $A_i \le 2$ ($1 \le i \le N$)，$B_j \le 2$ ($1 \le j \le N$)．
4. (25点) $A_i < A_{i+1}$ ($1 \le i \le N-1$)，$B_j < B_{j+1}$ ($1 \le j \le N-1$)．
5. (30点) 追加の制約はない．

예제 입력 1

3
5 2 5
5 3 1

예제 출력 1

5 4

最終的に各マスに塗られる色の番号は以下のようになる．

5 3 1
2 3 3
5 5 5

最も多くのマスに塗られた色の番号は5であり，これは4個のマスに塗られているため，5と4を空白区切りで出力する．

この入力例は小課題1, 2, 5の制約を満たす．

예제 입력 2

3
1 7 8
1 3 5

예제 출력 2

8 3

最終的に各マスに塗られる色の番号は以下のようになる．

1 3 5
7 7 7
8 8 8

最も多くのマスに塗られた色の番号は7と8であり，それぞれ3個のマスに塗られている．2つの色のうち最も番号が大きい色は8であるため，8と3を空白区切りで出力する．

この入力例は小課題1, 2, 4, 5の制約を満たす．

예제 입력 3

4
2 1 2 1
2 1 1 2

예제 출력 3

2 10

この入力例は小課題1, 2, 3, 5の制約を満たす．