Problem Description

Maxwell has a chocolate bar he wants to share with his friends. The chocolate can be represented as a $2 \times N$ grid of small squares, with each square's deliciousness denoted by a $2 \times N$ integer array $T_{i,j}$. Maxwell wants to divide the entire chocolate into several connected blocks, where each block has the same average deliciousness. He wonders what the maximum number of such connected blocks he can create.

A block is considered connected if every square in the block can be reached from any other square in the block by moving up, down, left, or right.

Input Format

The first line of input contains a positive integer $N$, representing the length of the chocolate.

The second line contains $N$ space-separated integers, where the $j$-th integer represents the deliciousness $T_{1,j}$ of the $j$-th square in the first row.

Similarly, the third line contains $N$ space-separated integers, where the $j$-th integer represents the deliciousness $T_{2,j}$ of the $j$-th square in the second row.

Output Format

Output a single integer, which is the maximum number of connected blocks Maxwell can divide the chocolate into.

Sample Input and Output

Sample Input #1

2
5 4
6 5

Sample Output #1

2

Sample Input #2

5
1 0 1 2 0
0 2 0 3 1

Sample Output #2

5

Notes

[Sample 1 Explanation]

Dividing the chocolate into 2 blocks is optimal. One way to do this is to make the bottom-right square a block and the remaining three squares another block, as shown in the diagram.

Each block has an average deliciousness of 5.

[Sample 2 Explanation]

One way to achieve equal average deliciousness for each block is shown in the diagram.

Note that each block has an average deliciousness of 1.

[Data Range]

This problem uses subtask scoring.

For all data, it is guaranteed that $1 \leq N \leq 2 \times 10^5$ and $0 \leq T_{i,j} \leq 10^8$.

The following table shows the scoring distribution for 15 points:

见题面 Input 部分

见题面 Output 部分