Robust Non-decreasing Subsequence

Jia Yuan's older sister recently celebrated her birthday, and her friends gifted her an interesting toy. The toy displays a sequence of numbers. Some items in the sequence may change their values; however, at any given time, at most one element changes. Jia Yuan has thoroughly studied all possible single‐change variations. Now she asks you for help: Is it possible to choose a subsequence (not necessarily contiguous) such that in every scenario—whether the original sequence or any one of the possible single-change variations—the subsequence remains non-decreasing? Your task is to output the length of the longest such subsequence.

Note that for any two consecutive indices i and j (with i < j) chosen in the subsequence, let A[i] and A[j] be their original values, and B[i] and B[j] be their alternate values (when the element changes). Since at most one element changes at a time, the subsequence must be robust in the following cases:

• No change: A[i] ≤ A[j].
• Only the left element changes: B[i] ≤ A[j].
• Only the right element changes: A[i] ≤ B[j].

Your solution should compute the maximum possible length of a subsequence which satisfies the above conditions for every adjacent pair.

Input:

1. An integer n representing the length of the sequence.
2. A line with n integers, representing the original sequence A.
3. A line with n integers, representing the alternate values B corresponding to each element. (For elements that cannot change, the alternate value will be the same as the original value.)

Output:

Output a single integer representing the length of the longest robust non-decreasing subsequence.

Constraints:

• 1 ≤ n ≤ 103 (for example)
• The values in the sequence are integers.

Example Explanation:

Consider the following three test cases:

Test Case 1:
Input:
5
1 2 3 4 5
1 2 3 4 5
Output:
5

Test Case 2:
Input:
5
5 4 3 2 1
5 4 3 2 1
Output:
1

Test Case 3:
Input:
5
1 3 2 4 3
2 2 4 5 3
Output:
3

inputFormat

The first line contains an integer n, which is the length of the sequence. The second line contains n space-separated integers representing the original sequence A. The third line contains n space-separated integers representing the alternate sequence B (when an element can change). It is guaranteed that at most one element can change at any time.

outputFormat

Output a single integer: the maximum length of a subsequence that is non-decreasing under the original sequence and every possibility where exactly one element is changed.

sample

5
1 2 3 4 5
1 2 3 4 5

5

</p>