题目背景

译自 第24回日本情報オリンピック 本選 T1。

题目描述

要把一个 $N\times N$ 的网格图染色。我们记第 $i$ 行第 $j$ 列的格子为 $(i,j)$。

第一行和第一列的格子已经被染了色。具体地，$\forall 1\le i\le N$，格子 $(i,1)$ 的颜色为 $A_i$，格子 $(1,i)$ 的颜色为 $B_i$。根据定义 $A_1=B_1$。

对于剩下的格子，考虑如下的染色过程：

• 对于 $i=2,3,\cdots,N$，按如下的方案染色第 $i$ 行：
  • 对于 $j=2,3,\cdots,N$，按如下的方案染色格子 $(i,j)$：
    • 记 $\operatorname{color}(i,j)$ 为格子 $(i,j)$ 的颜色（对应的数字）。则 $\operatorname{color}(i,j)=\max(\operatorname{color}(i-1,j),\operatorname{color}(i,j-1))$。

在染色结束后，输出哪种颜色被染在最多的格子上，以及这种颜色被染在多少个格子上。如果有多种颜色，输出数字最大的那种。

输入格式

如下所示：

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

输出格式

输出一行两个整数，以空格分隔：

• 第一个整数，表示被染在最多的格子上的颜色。如果有多种颜色，输出数字最大的那种。
• 第二个整数，表示这种颜色被染在了多少个格子上。

3
5 2 5
5 3 1

5 4

3
1 7 8
1 3 5

8 3

4
2 1 2 1
2 1 1 2

2 10

提示

样例解释

样例 $1$ 解释

最后各个格子的颜色如下所示：

$5$	$3$	$1$
$2$	$3$
$5$

颜色 $5$ 被染在了 $4$ 个格子上，所以输出 $\texttt{5 4}$。

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

样例 $2$ 解释

最后各个格子的颜色如下所示：

$1$	$3$	$5$
$7$
$8$

颜色 $7,8$ 都被染在了 $3$ 个格子上，所以输出较大的 $\texttt{8 3}$。

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

样例 $3$ 解释

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

数据范围

• $2\le N\le 2\times 10^5$。
• $1\le A_i\le 10^9$（$1\le i\le N$）。
• $1\le B_i\le 10^9$（$1\le i\le N$）。
• $A_1=B_1$。
• 输入的值全部是整数。

子任务

1. （15pts）$N\le 500$，$A_i,B_i\le 10^5$（$1\le i\le N$）。
2. （10pts）$N\le 500$。
3. （20pts）$A_i,B_i\le 2$（$1\le i\le N$）。
4. （25pts）$A_i\lt A_{i+1},B_i\lt B_{i+1}$（$\forall 1\le i\le N-1$）；
5. （30pts）无额外限制。