Synchronized Inversions - Repovive Starter Round 4 | 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$ .

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

15E. Synchronized Inversions

Constraints

Input

Output

Samples

15E. Synchronized Inversions

Constraints

Input

Output

Samples