Sums of Numbers 8

Interview

Time limit1sMemory limit512 MB

Summary

Count the index pairs (i, j) where the sum of A over the range [i, j] equals the sum of B over the same range.

Problem

Given two integer sequences of the same length, $A = \{A_1, A_2, \ldots, A_N\}$ and $B = \{B_1, B_2, \ldots, B_N\}$ .

Find the number of pairs of positive integers $(i, j)$ ( $i \leq j$ ) that satisfy $A_i + A_{i+1} + \cdots + A_j = B_i + B_{i+1} + \cdots + B_j$ .

The first line contains a positive integer $N$ .

The second line contains $N$ positive integers $A_i$ in order from $A_1$ to $A_N$ , separated by spaces.

The third line contains $N$ positive integers $B_i$ in order from $B_1$ to $B_N$ , separated by spaces.

Print the number of pairs of positive integers $(i, j)$ ( $i \leq j$ ) that satisfy $A_i + A_{i+1} + \cdots + A_j = B_i + B_{i+1} + \cdots + B_j$ .

The answer can exceed the range of a 32-bit integer type, so use an integer type that fits your language.

Example 3

Input

6
23 13 31 17 29 19
23 13 31 17 29 19

Expected output