分数: 500 点
问题陈述
N 史莱姆排成一行。尺寸 i左边第一个史莱姆是 P_i,其颜色为 C_i。在这里,史莱姆的大小是不同的。
当满足以下条件时,史莱姆序列被称为好序列:
- 通过重复执行交换两个相邻史莱姆的位置的操作 不同颜色,可以按大小升序排列史莱姆。
要使史莱姆序列成为良好的序列,您可以执行以下操作任意次数(可能为零):
- 选择一个史莱姆,然后将史莱姆的颜色更改为之间的任何整数 1 和 N,包括在内。此操作成本 x,其中 x 是此操作之前史莱姆的颜色。
求使史莱姆序列成为良好序列所需的最小总成本。
约束
- 所有输入值均为整数。
- 1 \leq N \leq 2\times 10^5
- 1\leq P_i \leq N
- 1\leq C_i \leq N
- P 是一个排列 (1,\ldots,N).
输入
输入由标准输入按以下格式给出:
N P_1 \ldots P_N C_1 \ldots C_N
输出
输出答案。
示例输入 1
4 3 1 2 4 1 2 1 3
示例输出 1
1
更改颜色 3-rd 史莱姆 2。然后,通过交换 1-st 和 2-nd 史莱姆,并交换 2-nd 和 3-rd 史莱姆,可以按大小升序排列史莱姆,使其成为一个良好的序列。
所需成本为 1,因为颜色 3-rd 史莱姆在手术前不久 1.
示例输入 2
10 3 7 10 1 9 5 4 8 6 2 6 4 8 4 6 8 8 4 8 8
示例输出 2
28