Counting Special Segments

White was bored, so she presented the following problem. You are given two sequences of n numbers: a and b. A segment defined by indices l and r (with 1 ≤ l ≤ r ≤ n) is considered special if

\(b_l \equiv b_r \pmod{\max_{l \le i \le r} a_i}\)

Count the total number of such pairs (l, r).

inputFormat

The first line contains an integer n (the number of elements).

The second line contains n space-separated integers representing the sequence a.

The third line contains n space-separated integers representing the sequence b.

outputFormat

Output a single integer representing the number of pairs (l, r) (with 1 ≤ l ≤ r ≤ n) that satisfy the condition

\(b_l \equiv b_r \pmod{\max_{l \le i \le r} a_i}\)

sample

3
1 2 3
4 5 6

3