题目描述

题目译自 JOI 2025 Final T1 「色塗り / Grid Coloring」

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$ 行的格子；
• 对于每一行依次处理 $j = 2, 3, \ldots, N$ 列的格子；
  • 将格子 $(i, j)$ 填上 $(i-1, j)$ 和 $(i, j-1)$ 这两个格子中颜色编号较大的颜色。如果两个格子的颜色编号相同，则使用相同的颜色。

K 理事长希望在所有 $N^2$ 个格子都填色完毕后，找到最多格子涂上的颜色编号，以及涂上该颜色的格子的数量。

给定网格的大小以及第 $1$ 列和第 $1$ 行的颜色信息，编写一个程序，求出涂上最多格子的颜色编号及其对应的格子数量。如果有多个颜色编号符合条件，请输出编号最大的颜色。

输入格式

第一行包含一个整数 $N$。

第二行包含用空格分隔的 $N$ 个整数 $A_1, A_2, \ldots A_N$。

第三行包含用空格分隔的 $N$ 个整数 $B_1, B_2, \ldots B_N$。

输出格式

输出涂上最多格子的颜色编号及其对应的格子数量。若存在多个颜色编号符合条件，则输出编号最大的颜色。

3
5 2 5
5 3 1

5 4

最终，每个格子的颜色编号如下：

$$\begin{array}{|l|l|l|} \hline 5 & 3 & 1 \\ \hline 2 & 3 & 3 \\ \hline 5 & 5 & 5 \\ \hline \end{array} $$

最多的颜色是 $5$，且涂在了 $4$ 个格子上，因此输出 $5$ 和 $4$。

这个样例满足子任务 $1,2,5$ 的限制。

3
1 7 8
1 3 5

8 3

最终，每个格子的颜色编号如下：

$$\begin{array}{|l|l|l|} \hline 1 & 3 & 5 \\ \hline 7 & 7 & 7 \\ \hline 8 & 8 & 8 \\ \hline \end{array} $$

最多的颜色是 $7$ 和 $8$，且分别涂在了 $3$ 个格子上。因为 $8$ 的编号较大，所以输出 $8$ 和 $3$。

这个样例满足子任务 $1,2,4,5$ 的限制。

4
2 1 2 1
2 1 1 2

2 10

这个样例满足子任务 $1,2,3,5$ 的限制。

数据范围与提示

对于所有输入数据，满足：

• $2 \le N \le 200000$。
• $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 100000\,(1 \le i \le N), B_{j} \le 100000\,(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$	无附加限制