Contest: Task: Related: TaskB TaskD

Score : $300$ points

We have two permutations $P$ and $Q$ of size $N$ (that is, $P$ and $Q$ are both rearrangements of $(1,~2,~...,~N)$).

There are $N!$ possible permutations of size $N$. Among them, let $P$ and $Q$ be the $a$-th and $b$-th lexicographically smallest permutations, respectively. Find $|a - b|$.

For two sequences $X$ and $Y$, $X$ is said to be lexicographically smaller than $Y$ if and only if there exists an integer $k$ such that $X_i = Y_i~(1 \leq i < k)$ and $X_k < Y_k$.

- $2 \leq N \leq 8$
- $P$ and $Q$ are permutations of size $N$.

Input is given from Standard Input in the following format:

$N$ $P_1$ $P_2$ $...$ $P_N$ $Q_1$ $Q_2$ $...$ $Q_N$

Print $|a - b|$.

3 1 3 2 3 1 2

3

There are $6$ permutations of size $3$: $(1,~2,~3)$, $(1,~3,~2)$, $(2,~1,~3)$, $(2,~3,~1)$, $(3,~1,~2)$, and $(3,~2,~1)$. Among them, $(1,~3,~2)$ and $(3,~1,~2)$ come $2$-nd and $5$-th in lexicographical order, so the answer is $|2 - 5| = 3$.

8 7 3 5 4 2 1 6 8 3 8 2 5 4 6 7 1

17517

3 1 2 3 1 2 3

0