题目描述

要把一个 $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$ 行第 $j$ 列的格子，其中满足 $i\geq 2,j\geq 2$。
  • 记 $\operatorname{color}(i,j)$ 为格子 $(i,j)$ 的颜色（对应的数字）。则：

$$\operatorname{color}(i,j)=\max(\operatorname{color}(i-1,j),\operatorname{color}(i,j-1))$$

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

输入格式

第一行输入整数 $n$。

接下来一行输入 $n$ 个空格隔开的整数表示 $a_1,a_2,\cdots,a_n$。

接下来一行输入 $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

提示

数据范围

对于 $100\%$ 的数据，满足以下限制：

• $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$	$n\le 500$，$a_i,b_i\le 10^5$	$15$
$2$	$n\le 500$	$10$
$3$	$a_i,b_i\le 2$	$20$
$4$	$a_i\lt a_{i+1},b_i\lt b_{i+1}$	$25$
$5$	无	$30$

样例 $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$ 的限制。