题目描述

$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$ 番目の球を入れ替える。

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

输入格式

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

$N$ $C_1$ $C_2$ $\ldots$ $C_N$ $X_1$ $X_2$ $\ldots$ $X_N$

输出格式

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

题目大意

题目大意

从左到右排列着 $N$ 个球，第 $i$ 个球上标着两个数 $C_i$ 与 $X_i$ .

Ta的目标是将这个球的序列重新排序，使得整个序列成为一个按 $X$ 值排序。

其中，Ta的操作如下：

选择一个正整数 $i(i<N)$ ；

若 $C_i=C_{i+1}$ 交换 $i$ 和 $i+1$ 两个位置不需要花费任何代价。

否则，花费 $1$ 的代价

求Ta达成目标所需的最小代价~

数据范围

$2\leq N\leq 3\times10^5$

$1\leq C_i,X_i\leq N$

所有输入数据皆为整数。

样例解释

$(C,X)$

样例1：

交换 $1,2$ ，序列 $(5,2), (1,3), (2,1), (2,2), (1,1)$ ；

交换 $2,3$ ，序列 $(5,2), (2,1), (1,3), (2,2), (1,1)$ ；

交换 $3,4$ ，序列 $(5,2), (2,1), (2,2), (1,3), (1,1)$ ；

交换 $4,5$ ，序列 $(5,2), (2,1), (2,2), (1,1), (1,3)$ ；

交换 $3,4$ ，序列 $(5,2), (2,1), (1,1), (2,2), (1,3)$ ；

交换 $1,2$ ，序列 $(2,1), (5,2), (1,1), (2,2), (1,3)$ ；

交换 $2,3$ ，序列 $(2,1), (1,1), (5,2), (2,2), (1,3)$ ；

代价最小为 $6$ ，第 $4$ 次操作不需要代价。

样例2：

所有球的颜色一样，不需要代价。

样例3：

已经排好序了。

5
1 5 2 2 1
3 2 1 2 1

6

3
1 1 1
3 2 1

0

3
3 1 2
1 1 2

0

提示

制約

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

Sample Explanation 1

球の情報を $(色,\ 整数)$ で表すとします。 最初の状態は $(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$ であるためコストがかからないことに注意してください。

Sample Explanation 2

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

Sample Explanation 3

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