Maximize Matching Elements via Maximum Propagation

Given two sequences of integers A and B of length \( N \), you are allowed to perform the following operation any number of times:

Choose a contiguous interval (subarray) of length at least 2, and assign every number in that interval the maximum value originally present in that interval. In other words, if you choose an interval \( [l, r] \) (with \( r-l+1\ge2 \)) and let \( M=\max\{A_l, A_{l+1},\dots,A_r\} \), then after the operation, for every \( l\le i\le r \), set \( A_i=M \).

Your goal is to perform a (possibly empty) sequence of such operations on the initial sequence A so that for as many indices as possible the final value equals \( B_i \); that is, you want \( A_i=B_i \) to hold. Note that an operation always increases some values (or leaves them unchanged) as it propagates the maximum in the chosen interval, so it is impossible to decrease any value.

Important observations:

• For any index \( i \) to eventually satisfy \( A_i=B_i \), it is necessary that \( B_i\ge A_i \). Otherwise, since the operations can only increase values, you cannot change \( A_i \) to a smaller number.
• The operation can only be applied on an interval of at least two elements. Therefore, a single index that is wrong cannot be fixed by itself; however, if it is adjacent to an index that already has the target value, you can choose an interval covering both indices to update them.
• An operation can only propagate a value \( v \) if the chosen interval contains at least one element whose value is already \( v \) (so that the maximum is \( v \)).

A natural strategy is to consider contiguous blocks where \( B \) is constant. For each maximal contiguous block in \( B \) with constant value \( v \):

• If the block length is 1 (a single element), you can only count it if \( A_i \) already equals \( v \), because you cannot apply an operation on a single element.
• If the block length is at least 2, then if there is at least one index in the block where \( A_i=v \) initially, you can use that index to propagate \( v \) to the whole block by applying one operation over the block.

Compute the maximum number of indices that can satisfy \( A_i=B_i \) after applying an optimal sequence of operations.

Input Format: The first line contains an integer \( N \) (the length of the sequences). The second line contains \( N \) space-separated integers representing the sequence A. The third line contains \( N \) space-separated integers representing the sequence B.

Output Format: Output a single integer, the maximum number of indices \( i \) such that you can have \( A_i = B_i \) after the operations.

inputFormat

The input begins with a line containing an integer \( N \) (\( 1\le N\le 10^5 \)).

The second line contains \( N \) integers \( A_1, A_2, \dots, A_N \).

The third line contains \( N \) integers \( B_1, B_2, \dots, B_N \).

outputFormat

Output a single integer representing the maximum number of indices \( i \) for which you can achieve \( A_i=B_i \) after applying the allowed operations.

sample

5
1 2 3 4 5
1 2 2 4 5

5