P11662 [JOI 2025 Final] 方格染色 / Grid Coloring

译自 [第24回日本情報オリンピック 本選](https://contests.ioi-jp.org/joi-ho-2025/index.html) 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$

输出一行两个整数，以空格分隔： - 第一个整数，表示被染在最多的格子上的颜色。如果有多种颜色，输出数字最大的那种。 - 第二个整数，表示这种颜色被染在了多少个格子上。

### 样例解释 #### 样例 $1$ 解释 最后各个格子的颜色如下所示： | $5$ | $3$ | $1$ | | :--: | :--: | :--: | | $2$ | $3$ | $3$ | | $5$ | $5$ | $5$ | 颜色 $5$ 被染在了 $4$ 个格子上，所以输出 $\texttt{5 4}$。 该样例满足子任务 $1,2,5$ 的限制。 #### 样例 $2$ 解释 最后各个格子的颜色如下所示： | $1$ | $3$ | $5$ | | :--: | :--: | :--: | | $7$ | $7$ | $7$ | | $8$ | $8$ | $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）无额外限制。