102615: [AtCoder]ABC261 F - Sorting Color Balls

Problem Statement

There are $N$ balls arranged from left to right. The color of the $i$-th ball from the left is Color $C_i$, and an integer $X_i$ is written on it.

Takahashi wants to rearrange the balls so that the integers written on the balls are non-decreasing from left to right. In other words, his objective is to reach a situation where, for every $1\leq i\leq N-1$, the number written on the $(i+1)$-th ball from the left is greater than or equal to the number written on the $i$-th ball from the left.

For this, Takahashi can repeat the following operation any number of times (possibly zero):

Choose an integer $i$ such that $1\leq i\leq N-1$.
If the colors of the $i$-th and $(i+1)$-th balls from the left are different, pay a cost of $1$. (No cost is incurred if the colors are the same).
Swap the $i$-th and $(i+1)$-th balls from the left.

Find the minimum total cost Takahashi needs to pay to achieve his objective.

Constraints

• $2 \leq N \leq 3\times 10^5$
• $1\leq C_i\leq N$
• $1\leq X_i\leq N$
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

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

Output

Print the minimum total cost Takahashi needs to pay to achieve his objective, as an integer.

Sample Input 1

5
1 5 2 2 1
3 2 1 2 1

Sample Output 1

6

Let us represent a ball as $($Color$,$ Integer$)$. The initial situation is $(1,3)$, $(5,2)$, $(2,1)$, $(2,2)$, $(1,1)$. Here is a possible sequence of operations for Takahashi:

• Swap the $1$-st ball (Color $1$) and $2$-nd ball (Color $5$). Now the balls are arranged in the order $(5,2)$, $(1,3)$, $(2,1)$, $(2,2)$, $(1,1)$.
• Swap the $2$-nd ball (Color $1$) and $3$-rd ball (Color $2$). Now the balls are arranged in the order $(5,2)$, $(2,1)$, $(1,3)$, $(2,2)$, $(1,1)$.
• Swap the $3$-rd ball (Color $1$) and $4$-th ball (Color $2$). Now the balls are in the order $(5,2)$, $(2,1)$, $(2,2)$, $(1,3)$, $(1,1)$.
• Swap the $4$-th ball (Color $1$) and $5$-th ball (Color $1$). Now the balls are in the order $(5,2)$, $(2,1)$, $(2,2)$, $(1,1)$, $(1,3)$.
• Swap the $3$-rd ball (Color $2$) and $4$-th ball (Color $1$). Now the balls are in the order$(5,2)$, $(2,1)$, $(1,1)$, $(2,2)$, $(1,3)$.
• Swap the $1$-st ball (Color $5$) and $2$-nd ball (Color $2$). Now the balls are in the order $(2,1)$, $(5,2)$, $(1,1)$, $(2,2)$, $(1,3)$.
• Swap the $2$-nd ball (Color $5$) and $3$-rd ball (Color $1$). Now the balls are in the order $(2,1)$, $(1,1)$, $(5,2)$, $(2,2)$, $(1,3)$.

After the last operation, the numbers written on the balls are $1,1,2,2,3$ from left to right, which achieves Takahashi's objective.

The $1$-st, $2$-nd, $3$-rd, $5$-th, $6$-th, and $7$-th operations incur a cost of $1$ each, for a total of $6$, which is the minimum. Note that the $4$-th operation does not incur a cost since the balls are both in Color $1$.

Sample Input 2

3
1 1 1
3 2 1

Sample Output 2

0

All balls are in the same color, so no cost is incurred in swapping balls.

Sample Input 3

3
3 1 2
1 1 2

Sample Output 3

0

Takahashi's objective is already achieved without any operation.

问题描述

从左到右有N个球。从左数第i个球的颜色为Color C_i，球上写有一个整数X_i。

高桥想要重新排列这些球，使得球上写的整数从左到右是递增的。也就是说，他的目标是要达到一种情况，对于每个$1\leq i\leq N-1$，从左数第$(i+1)$个球上的数字大于或等于第i个球上的数字。

为了实现这个目标，高桥可以重复执行以下操作任意次数（包括零次）：

选择一个整数i，满足$1\leq i\leq N-1$。

如果从左数第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$

输出

输出高桥需要支付的最小总费用，作为整数。

样例输入1

5
1 5 2 2 1
3 2 1 2 1

样例输出1

6

让我们将一个球表示为($Color$,$Integer$)。初始情况为(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。

样例输入2

3
1 1 1
3 2 1

样例输出2

0

所有球都是相同颜色的，因此在交换球时不会产生费用。

样例输入3

3
3 1 2
1 1 2

样例输出3

0

高桥的目标已经实现，无需执行任何操作。