Background

$$Years of walking pass in quiet peace,$$ $$Under the ancient dark-blue sky.$$ $$Softly I begin to sing,$$ $$Of that wind bird.$$ $$But you are nowhere to be seen.$$

Problem Description

You are given $n$, and $n$ integers $a_i$ ($1\le i\le n$), and $n$ integers $b_i$ ($1\le i\le n$).

Now, for a sequence $S$ of length $n$, the following rules apply:

• $S_i = a_i$ or $b_i$.

• For all $S_i$ ($1\le i\le n$), if $S_i > S_{i-1}$ and $S_i > S_{i+1}$, then $S_i$ is called a peak. In particular, $S_0 = S_{n+1} = 0$.

You need to find: the maximum number of peaks, and the maximum range when the number of peaks is maximized.

Range: the difference between the maximum value and the minimum value in a sequence.

Updated: $S_0$ and $S_{n+1}$ do not participate in the range calculation.

Input Format

The first line contains an integer $n$.

The second line contains $n$ integers, representing $a_1, a_2 \dots a_n$.

The third line contains $n$ integers, representing $b_1, b_2 \dots b_n$.

Output Format

Output two lines in total.

The first line contains an integer representing the maximum number of peaks.

The second line contains an integer representing the maximum range when the maximum number of peaks is achieved.

6
9 1 2 4 7 10 
8 10 5 1 1 7 

3
9

10
6 13 27 31 34 59 64 66 71 95 
4 4 10 22 26 28 46 55 62 68 

5
91

Hint

Sample Explanation

In Sample 1, one valid sequence $S$ is $9,1,2,4,1,10$.

Among them, $S_1, S_4, S_6$ are peaks, and the range is $10-1=9$.

Constraints

Special property $A$: $\forall 1< i\le n$, $\text{max}(a_{i-1},b_{i-1})\le \text{min}(a_i,b_i)$.

Special property $B$: $\forall 1< i\le n$, $\text{min}(a_i,b_i)\le\text{max}(a_{i-1},b_{i-1})\le\text{max}(a_i,b_i)$.

Special property $C$: $\forall 1\le i\le n$, $a_i = k$, where $k$ is a positive integer.

For $100\%$ of the testdata, $1\le n\le 5\times10^5$, $1\le a_i,b_i\le 10^9$, and it is guaranteed that $a_i\ne b_i$.

Special reminder: This problem uses bundled subtask testing. You only get the score of a subtask if you pass all test points in that subtask.

Translated by ChatGPT 5