Count Order

AtCoder

IDabc150_c

Time2000ms

Memory256MB

Difficulty—

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|$. ## Constraints * $2 \leq N \leq 8$ * $P$ and $Q$ are permutations of size $N$. ## Input Input is given from Standard Input in the following format: $N$ $P_1$ $P_2$ $...$ $P_N$ $Q_1$ $Q_2$ $...$ $Q_N$ [samples] ## Notes 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$.

Samples

Input #1

3
1 3 2
3 1 2

Output #1

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$.

Input #2

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

Output #2

Input #3

3
1 2 3
1 2 3

Output #3

API Response (JSON)

{
  "problem": {
    "name": "Count Order",
    "description": {
      "content": "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 th",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "abc150_c"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "We have two permutations $P$ and $Q$ of size $N$ (that is, $P$ and $Q$ are both rearrangements of $(1,~2,~...,~N)$).\nThere are $N!$ possible permutations of size $N$. Among them, let $P$ and $Q$ be th...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments