← 返回题目列表

AtCoder · arc206_b

B. 史莱姆交换

中文机器翻译题面 查看原题

分数: 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