Problem Description

Maxwell has a chocolate bar that he wants to share with his friends. The chocolate bar can be viewed as a $2 \times N$ grid of small squares, and the tastiness of each square is given by a $2 \times N$ integer array $T_{i,j}$. Maxwell wants to divide the entire chocolate bar into several connected components, such that the average tastiness of the squares in each connected component is the same. Maxwell wants to know the maximum number of connected components he can partition the chocolate bar into, under the rules above.

A part is considered a connected component if every square in it can be reached by moving up, down, left, or right.

Input Format

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

The second line contains $N$ space-separated integers. The $j$-th integer is the tastiness $T_{1,j}$ of the square in row 1 and column $j$.

Similarly, the third line contains $N$ space-separated integers. The $j$-th integer is the tastiness $T_{2,j}$ of the square in row 2 and column $j$.

Output Format

Output one integer, representing the maximum number of connected components Maxwell can cut the chocolate bar into.

2
5 4
6 5

2

5
1 0 1 2 0
0 2 0 3 1

5

Hint

Sample 1 Explanation

Partitioning the chocolate bar into $2$ parts is optimal. One way is to take the single square in the bottom-right corner as one connected component, and the remaining three squares as the second connected component, as shown below.

The average tastiness of each connected component is $5$.

Sample 2 Explanation

One way to partition the chocolate bar with equal averages is shown below:

Note that the average tastiness of each part is $1$.

Constraints

This problem uses bundled testdata.

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

The table below shows the distribution of $15$ points:

Translated by ChatGPT 5