Description

Given a sequence $A_i$ of length $N$, you can perform the following operation any number of times:

• Choose an interval of length at least $2$, such that all numbers in this interval are equal to the maximum value in this interval.

You need to use these operations to make $A_i = B_i$. Find the maximum number of positions that can be made to satisfy the requirement.

Input Format

The first line contains an integer $N$, representing the length of the sequence.
The second line contains $N$ integers, representing the sequence $A_i$.
The third line contains $N$ integers, representing the sequence $B_i$.

Output Format

Output one integer on a single line, representing the answer.

3
1 2 3
2 2 2

2

4
10 1 9 1
10 9 10 9

3

Hint

Sample 1 Explanation

You can choose to perform the operation on the interval $[1,2]$. At most $2$ numbers can satisfy the requirement.

Sample 2 Explanation

Either $A_2$ or $A_3$ can satisfy the requirement, but they cannot satisfy the requirement at the same time.

Constraints

This problem uses bundled testdata.

• Subtask 1 (14 pts): $N \le 10$.
• Subtask 2 (12 pts): $N \le 10^5$, all $B_i$ are equal.
• Subtask 3 (13 pts): $N \le 5000$, $A_i$ is a strictly increasing sequence.
• Subtask 4 (23 pts): $N \le 10^5$, all $A_i$ are pairwise distinct.
• Subtask 5 (16 pts): $N \le 200$.
• Subtask 6 (22 pts): $N \le 5000$.

For $100\%$ of the testdata:

• $2 \le N$.
• $1 \le A_i \le 10^9$.
• $1 \le B_i \le 10^9$.

Note

Translated from eJOI 2020 Day1 C Exam。

Translated by ChatGPT 5