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