彩色球的排序

题目描述

有 $N$ 个球从左到右排列。 从左数第 $i$ 个球的颜色为颜色 $C_i$,上面写着整数 $X_i$。

Takahashi 希望重新排列这些球,使得从左到右写在球上的整数非递减。 换句话说,他的目标是达到如下状态:对于所有 $1 \le i \le N-1$,从左数第 $(i+1)$ 个球上的数字大于或等于从左数第 $i$ 个球上的数字。

为此,Takahashi 可以重复进行以下操作任意次(可以为 $0$ 次):

选择一个满足 $1 \le i \le N-1$ 的整数 $i$。

如果从左数第 $i$ 个球和第 $(i+1)$ 个球的颜色不同,则支付 $1$ 的费用。 (如果颜色相同,则不产生费用。)

交换从左数第 $i$ 个球和第 $(i+1)$ 个球。

求 Takahashi 为达成目标所需支付的最小总费用。

输入格式

输入按以下格式从标准输入给出：

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

输出格式

输出 Takahashi 为达成目标所需支付的最小总费用,以整数形式。

样例

5
1 5 2 2 1
3 2 1 2 1

6

用 $(\text{颜色},\text{整数})$ 表示一个球。 初始状态为 $(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$,达成了 Takahashi 的目标。

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

Takahashi 不进行任何操作就已经达成了目标。

数据范围

• $2 \le N \le 3 \times 10^5$
• $1 \le C_i \le N$
• $1 \le X_i \le N$
• 输入均为整数