配点 : $500$ 点

問題文

$N$ 個の球が左右一列に並んでいます。 左から $i$ 番目の球の色は色 $C_i$ であり、整数 $X_i$ が書かれています。

高橋君の目標は球を左から右に見た時に書かれている数が非減少になるように球を並べ替えることです。 言い換えれば、高橋君の目標は、任意の $1\leq i\leq N-1$ について、左から $i+1$ 番目の球に書かれている数 が左から $i$ 番目に書かれている数以上であるようにすることです。

高橋君は目標を達成するために、次の操作を好きなだけ（ $0$ 回でも良い ）繰り返すことができます。

$1\leq i\leq N-1$ をみたす整数 $i$ を選ぶ。 左から $i$ 番目の球と $i+1$ 番目の球の色が異なっているならば、コストを $1$ 支払う。 （色が等しいならばコストを支払う必要は無い。） 左から $i$ 番目の球と $i+1$ 番目の球を入れ替える。

高橋君が目標を達成するために支払う必要のあるコストの最小値を求めてください。

制約

• $2 \leq N \leq 3\times 10^5$
• $1\leq C_i\leq N$
• $1\leq X_i\leq N$
• 入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

$N$

$C_1$ $C_2$ $\ldots$ $C_N$

$X_1$ $X_2$ $\ldots$ $X_N$

出力

高橋君が支払う必要のあるコストの最小値を整数で出力せよ。

5
1 5 2 2 1
3 2 1 2 1

6

球の情報を $(色, 整数)$ で表すとします。 最初の状態は $(1,3)$, $(5,2)$, $(2,1)$, $(2,2)$, $(1,1)$ です。 例えば、高橋君は次のように操作を行うことができます。

• 左から $1$ 番目の球 (色 $1$) と $2$ 番目の球 (色 $5$) を入れ替える。 球は左から $(5,2)$, $(1,3)$, $(2,1)$, $(2,2)$, $(1,1)$ となる。
• 左から $2$ 番目の球 (色 $1$) と $3$ 番目の球 (色 $2$) を入れ替える。 球は左から $(5,2)$, $(2,1)$, $(1,3)$, $(2,2)$, $(1,1)$ となる。
• 左から $3$ 番目の球 (色 $1$) と $4$ 番目の球 (色 $2$) を入れ替える。 球は左から $(5,2)$, $(2,1)$, $(2,2)$, $(1,3)$, $(1,1)$ となる。
• 左から $4$ 番目の球 (色 $1$) と $5$ 番目の球 (色 $1$) を入れ替える。 球は左から $(5,2)$, $(2,1)$, $(2,2)$, $(1,1)$, $(1,3)$ となる。
• 左から $3$ 番目の球 (色 $2$) と $4$ 番目の球 (色 $1$) を入れ替える。 球は左から $(5,2)$, $(2,1)$, $(1,1)$, $(2,2)$, $(1,3)$ となる。
• 左から $1$ 番目の球 (色 $5$) と $2$ 番目の球 (色 $2$) を入れ替える。 球は左から $(2,1)$, $(5,2)$, $(1,1)$, $(2,2)$, $(1,3)$ となる。
• 左から $2$ 番目の球 (色 $5$) と $3$ 番目の球 (色 $1$) を入れ替える。 球は左から $(2,1)$, $(1,1)$, $(5,2)$, $(2,2)$, $(1,3)$ となる。

最後の操作の後で球に書かれている数は左から順に $1,1,2,2,3$ となっているため、高橋君は目的を達成しています。

$1,2,3,5,6,7$ 回目の操作にコストが $1$ ずつかかるため、 このとき合計でコストは $6$ かかり、このときが最小となります。 $4$ 回目の操作では、入れ替えた球の色がともに色 $1$ であるためコストがかからないことに注意してください。

3
1 1 1
3 2 1

0

すべての球の色は同じであるため、球の入れ替えにコストがかかることはありません。

3
3 1 2
1 1 2

0

高橋君は一度も操作を行わずとも、目的を達成できています。