色塗り (Grid Coloring)

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

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

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

• \(i=2,3,\dots,N\) の順に，以下の手順で \(i\) 行目のマスに色を塗る．
  • \(j=2,3,\dots,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 \leqq N \leqq 200\,000\)．
• \(1 \leqq A_i \leqq 10^9\) (\(1 \leqq i \leqq N\))．
• \(1 \leqq B_j \leqq 10^9\) (\(1 \leqq j \leqq N\))．
• \(A_1 = B_1\)．
• 入力される値はすべて整数である．

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

JOI 2025 · JCIOI · CC BY-SA 4.0