P10705 Solitude (Solitude)

>$$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.$$

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.**

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 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**.

#### 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 | Subtask ID | $n$ | Special Property | Score | | :----------: | :----------: | :----------: | :----------: | | $0$ | $\le 20$ | $-$ | $10$ | | $1$ | $\le 2000$ | $-$ | $10$ | | $2$ | $\le 10^5$ | $A$ | $10$ | | $3$ | $\le 10^5$ | $B$ | $10$ | | $4$ | $\le 10^5$ | $C$ | $10$ | | $5$ | $\le 5\times10^5$ | $-$ | $50$ | 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