#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/contests/15/problems/E

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░██████████████████████████████████████████

Synchronized Inversions - Repovive Starter Round 4 | Repovive | Repovive

15E. Synchronized Inversions

2500 pts1s256 MB

You are given two permutations $a_1, a_2, \ldots, a_n$ and $b_1, b_2, \ldots, b_n$ .

In one operation, you choose two indices $i$ and $j$ with $1 \le i, j \le n$ , then perform both of the following swaps simultaneously:

swap $a_i$ and $a_j$ ,
swap $b_i$ and $b_j$ .

You may perform any number of operations, possibly zero.

For an array $c_1, c_2, \ldots, c_n$ , define $\operatorname{inv}(c)$ as the number of pairs $(i, j)$ such that $1 \le i < j \le n$ and $c_i > c_j$ .

Your task is to find how many distinct values of $\operatorname{inv}(a) + \operatorname{inv}(b)$ can be obtained after performing the operations.

Constraints

$1 \le n \le 2 \times 10^5$
$a_1, a_2, \ldots, a_n$ is a permutation of $1, 2, \ldots, n$
$b_1, b_2, \ldots, b_n$ is a permutation of $1, 2, \ldots, n$

Input

\begin{array}{l} n \\ a_1 \quad a_2 \quad \cdots \quad a_n \\ b_1 \quad b_2 \quad \cdots \quad b_n \end{array}

Output

Output a single integer, the number of distinct possible values of $\operatorname{inv}(a) + \operatorname{inv}(b)$ .

Samples

Input

3
1 2 3
1 2 3

Explanation

With no operation, the arrays stay $[1, 2, 3]$ and $[1, 2, 3]$ , so the total is $0$ .

Swapping indices $1$ and $2$ makes the arrays $[2, 1, 3]$ and $[2, 1, 3]$ , so the total is $2$ .

Swapping indices $1$ and $2$ , then indices $2$ and $3$ , makes the arrays $[2, 3, 1]$ and $[2, 3, 1]$ , so the total is $4$ .

Swapping indices $1$ and $3$ makes the arrays $[3, 2, 1]$ and $[3, 2, 1]$ , so the total is $6$ .

Thus there are $4$ possible values.

Output

Input

3
1 2 3
3 2 1

Explanation

With no operation, the arrays are $[1, 2, 3]$ and $[3, 2, 1]$ , and the total is $3$ .

Swapping indices $1$ and $2$ makes the arrays $[2, 1, 3]$ and $[2, 3, 1]$ , and the total is still $3$ .

Checking the other final arrangements gives the same total, so only $1$ value is possible.

Output

Input

4
1 2 3 4
1 3 2 4

Explanation

With no operation, the arrays stay $[1, 2, 3, 4]$ and $[1, 3, 2, 4]$ , so the total is $1$ .

For example, after swapping indices $1$ and $2$ , then indices $2$ and $4$ , the arrays become $[2, 4, 3, 1]$ and $[3, 4, 2, 1]$ , so the total is $9$ .

Output

You are given two permutations $a_1, a_2, \ldots, a_n$ and $b_1, b_2, \ldots, b_n$ .

In one operation, you choose two indices $i$ and $j$ with $1 \le i, j \le n$ , then perform both of the following swaps simultaneously:

swap $a_i$ and $a_j$ ,
swap $b_i$ and $b_j$ .

You may perform any number of operations, possibly zero.

For an array $c_1, c_2, \ldots, c_n$ , define $\operatorname{inv}(c)$ as the number of pairs $(i, j)$ such that $1 \le i < j \le n$ and $c_i > c_j$ .

Your task is to find how many distinct values of $\operatorname{inv}(a) + \operatorname{inv}(b)$ can be obtained after performing the operations.

$1 \le n \le 2 \times 10^5$
$a_1, a_2, \ldots, a_n$ is a permutation of $1, 2, \ldots, n$
$b_1, b_2, \ldots, b_n$ is a permutation of $1, 2, \ldots, n$

\begin{array}{l} n \\ a_1 \quad a_2 \quad \cdots \quad a_n \\ b_1 \quad b_2 \quad \cdots \quad b_n \end{array}

Output a single integer, the number of distinct possible values of $\operatorname{inv}(a) + \operatorname{inv}(b)$ .

With no operation, the arrays stay $[1, 2, 3]$ and $[1, 2, 3]$ , so the total is $0$ .

Swapping indices $1$ and $2$ makes the arrays $[2, 1, 3]$ and $[2, 1, 3]$ , so the total is $2$ .

Swapping indices $1$ and $2$ , then indices $2$ and $3$ , makes the arrays $[2, 3, 1]$ and $[2, 3, 1]$ , so the total is $4$ .

Swapping indices $1$ and $3$ makes the arrays $[3, 2, 1]$ and $[3, 2, 1]$ , so the total is $6$ .

Thus there are $4$ possible values.

With no operation, the arrays are $[1, 2, 3]$ and $[3, 2, 1]$ , and the total is $3$ .

Swapping indices $1$ and $2$ makes the arrays $[2, 1, 3]$ and $[2, 3, 1]$ , and the total is still $3$ .

Checking the other final arrangements gives the same total, so only $1$ value is possible.

With no operation, the arrays stay $[1, 2, 3, 4]$ and $[1, 3, 2, 4]$ , so the total is $1$ .

For example, after swapping indices $1$ and $2$ , then indices $2$ and $4$ , the arrays become $[2, 4, 3, 1]$ and $[3, 4, 2, 1]$ , so the total is $9$ .

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

15E. Synchronized Inversions

Constraints

Input

Output

Samples

15E. Synchronized Inversions

Constraints

Input

Output

Samples