Dragons

In ancient times, when dragons were not legends, to tame a dragon, one had to engage in a mental battle with it! When Chmyyyaks was taming his dragon, he gave it the following task. He solved it very quickly, but can you?

Two arrays of length $n$ are given. Let us define a good pair of subsegments of different arrays $l_1,r_1$ — a subsegment of the first array (denoted as $c$) and $l_2,r_2$ — a subsegment of the second array (denoted as $d$), satisfying the following properties:

1. $|c|=|d|$ — they have the same length.

2. ${\sum }_{i=1}^{|c|}f(c_i-d_i)=0$, where $f(x)=\{\begin{array}{ll}1,& x>0\\ 0,& x=0\\ -1,& x<0\end{array}$

In short, your task is simple — count the number of good pairs of subsegments.

Input

The first line contains exactly one integer $n(1\le n\le 10000)$ — the length of two arrays.

The second line contains $n$ integers $a_i(0\le a_i\le 10^9)$ — the elements of the first array.

The third line contains $n$ integers $b_i(0\le b_i\le 10^9)$ — the elements of the second array.

Output

Output only one integer – the answer to the problem.

Examples

Note

In the first sample

1. a pair of subsegments $[(1,1),(2,2)]$ is bad, cause $f(8-5)=1\ne 0$;

2. a pair of subsegments $[(1,2),(2,3)]$ is good, because $f(8-5)+f(1-2)=f(3)+f(-1)=0$.

In total there are 4 good pairs of subsegments: $\{[(1,2),(1,2)],[(1,2),(2,3)],[(2,3),(1,2)],[(2,3),(2,3)]\}$.

Scoring

1. ($7$ points): $n\le 100$;

2. ($14$ points): $n\le 500$;

3. ($22$ points): $n\le 1000,a_i\le 100$;

4. ($31$ points): $n\le 5000$

5. ($26$ points): no additional constraints;