Uolevi has found two matrices $A$ and $B$ of size $n\times n$. Every element in both matrices is either $0$ or $1$. They also have the following special property: if the element in $(i_0,j_0)$ is $1$, then for all $i$ and $j$ such that $i\geq i_0$ and $j\leq j_0$ the element in $(i, j)$ is also $1$.

Now Uolevi is wondering what happens if he multiplies $A$ with $B$. Particularly he is interested in how many non-zero elements $A\times B$ contains.

Can you help him to answer this question?

Input

In the first line you're given the integer $n$.

The second line contains $n$ non-decreasing integers $a_{1}, a_{2}, \dots, a_{n}$. These integers describe the matrix $A$. For $1 \leq x, y, \leq n$, let $A_{y,x} = 0$ if $a_y < x$, and otherwise one. It can be proven that every matrix with the given property can be presented this way.

The third line contains $n$ non-decreasing integers $b_{1}, b_{2}, \dots b_{n}$. These integers describe the matrix $B$, in the same way as the integers $a_{1}, \dots, a_{n}$ describe $A$.

Output

Output a single integer: the number of non-zero elements in $A\times B$.

Constraints

• $1\leq n\leq 2\cdot 10^5$
• $0\leq a_i, b_i\leq n$
• $a_i\leq a_{i+1}$
• $b_i\leq b_{i+1}$

Example

Input:

3
2 2 3
0 1 3

Output:

5