Problem Background

$$Walking through peaceful years,$$

$$The ancient sky in dark blue.$$

$$Softly singing,$$

$$That windbird.$$

$$But you are gone.$$

Problem Description

Given \( n \) and \( n \) integers \( a_i \) ( \( 1 \le i \le n \) ), \( n \) integers \( b_i \) ( \( 1 \le i \le n \) ).

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. Specifically, \( S_0 = S_{n+1} = 0 \).

Objective: Find the maximum number of peaks and the maximum range (difference between the maximum and minimum values) when achieving the maximum number of peaks.

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

Updated: \( S_0 \) and \( S_{n+1} \) are not included 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 consists of two lines.

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

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

Sample Input and Output

Sample Input #1

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

Sample Output #1

3
9

Sample Input #2

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

Sample Output #2

5
91

Notes

Sample Explanation

In Sample #1, one valid sequence \( S \) is \( 9, 1, 2, 4, 1, 10 \).

Here, \( S_1, S_4, S_6 \) are peaks, and the maximum range is \( 10 - 1 = 9 \).

Data Range

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 data, \(1 \le n \le 5 \times 10^5\), \(1 \le a_i, b_i \le 10^9\), and \(a_i \ne b_i\).

Special Note: This problem uses subtask-based scoring. You must pass all test cases of a subtask to earn the score for that subtask.

见题面 Input 部分

见题面 Output 部分