Problems
President K is designing a pattern on an N×N grid. Each cell is painted with a color represented by an integer. Let the cell in the i-th row (1 ≤ i ≤ N) and j-th column (1 ≤ j ≤ N) be denoted as (i, j).
Currently, the cells in the first row and the first column are already painted. Specifically, for every 1 ≤ i ≤ N, cell (i, 1) is painted with color Aᵢ, and for every 1 ≤ j ≤ N, cell (1, j) is painted with color Bⱼ, with the guarantee that A₁ = B₁.
For the remaining unpainted cells, President K will paint them according to the following procedure:
• For each i = 2, 3, …, N in order, paint the cells in the i-th row as follows:
◦ For each j = 2, 3, …, N in order, paint cell (i, j) with the larger of the two colors:
The color of cell (i − 1, j), or
* The color of cell (i, j − 1).
(If both colors are the same, paint the cell with that color.)
After all N² cells have been painted, President K wants to determine which color is painted on the largest number of cells and the number of cells painted with that color. If multiple colors are tied for the maximum count, output the one with the largest color number.
[Constrains]
2 ≤ N ≤ 200\ 000 1 ≤ A_i ≤ 10^9 (1 ≤ i ≤ N )1 ≤ B_j ≤ 10^9 (1 ≤ j ≤ N )A_1 = B_1 Given values are all integers.
Input
The first line contains an integer N.
The second line contains N space-separated integers A₁, A₂, …, A_N, representing the colors of the first column.
The third line contains N space-separated integers B₁, B₂, …, B_N, representing the colors of the first row, with the guarantee that A₁ = B₁.
Output
Print two integers on one line separated by a space:
The color number that appears on the largest number of cells, and
The number of cells painted with that color.
(If there is a tie for the most frequent color, output the one with the largest color number.)
Subtask
| # | Score | Condition |
|---|---|---|
| #1 | 15 | N ≤ 500, Aᵢ ≤ 10⁵ (1 ≤ i ≤ N), Bⱼ ≤ 10⁵ (1 ≤ j ≤ N). |
| #2 | 10 | N ≤ 500 |
| #3 | 20 | All Aᵢ and Bⱼ are either 1 or 2 |
| #4 | 25 | A₁, A₂, …, A_N and B₁, B₂, …, B_N are each strictly increasing |
| #5 | 30 | No additional constraints |
Example #1
3
5 2 5
5 3 1
5 4
The grid is painted as follows:
5 3 1
2 3 3
5 5 5
Color 5 appears in 4 cells (in the first row and the entire third row), which is the highest frequency. Hence, the output is "5 4".
Example #2
3
1 7 8
1 3 5
8 3
The grid is painted as follows:
1 3 5
7 7 7
8 8 8
Both colors 7 and 8 appear 3 times, but since 8 is larger, the output is "8 3".
Example #3
4
2 1 2 1
2 1 1 2
2 10
You must sign in to write code.