Mike and !Mike are old childhood rivals, they are opposite in everything they do, except programming. Today they have a problem they cannot solve on their own, but together (with you) — who knows?

Every one of them has an integer sequences $*a*$ and $*b*$ of length $*n*$. Being given a query of the form of pair of integers $(*l*, *r*)$, Mike can instantly tell the value of while !Mike can instantly tell the value of .

Now suppose a robot (you!) asks them all possible different queries of pairs of integers $(*l*, *r*)$ $(1 ≤ *l* ≤ *r* ≤ *n*)$ (so he will make exactly $*n*(*n* + 1) / 2$ queries) and counts how many times their answers coincide, thus for how many pairs is satisfied.

How many occasions will the robot count?

Input

The first line contains only integer $*n*$ ($1 ≤ *n* ≤ 200 000$).

The second line contains $*n*$ integer numbers $*a*_{1}, *a*_{2}, ..., *a*_{*n*}$ ($- 10^{9} ≤ *a*_{*i*} ≤ 10^{9}$) — the sequence $*a*$.

The third line contains $*n*$ integer numbers $*b*_{1}, *b*_{2}, ..., *b*_{*n*}$ ($- 10^{9} ≤ *b*_{*i*} ≤ 10^{9}$) — the sequence $*b*$.

Output

Print the only integer number — the number of occasions the robot will count, thus for how many pairs is satisfied.

Note

The occasions in the first sample case are:

1.$*l* = 4$,$*r* = 4$ since $*max*{2} = *min*{2}$.

2.$*l* = 4$,$*r* = 5$ since $*max*{2, 1} = *min*{2, 3}$.

There are no occasions in the second sample case since Mike will answer $3$ to any query pair, but !Mike will always answer $1$.