B - Slime Swap Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 500 点

問題文

N 匹のスライムが一列に並んでいます．左から i 番目のスライムの大きさは P_i で，色は C_i です．ここで，スライムの大きさは相異なります．

スライムの列が以下の条件を満たすとき良い列と呼びます．

  • 隣接する異なる色のスライム二匹の位置を入れ替える操作を繰り返して，スライムを大きさの昇順に並べることができる．

あなたはスライムの列を良い列にするため，以下の操作を 0 回以上好きな回数行うことができます．

  • スライムを一匹選び，そのスライムの色を 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 番目のスライムの色を 2 に変えます．すると，1 番目のスライムと 2 番目のスライムを入れ替え，2 番目のスライムと 3 番目のスライムを入れ替えることで，スライムを大きさの昇順に並べることができるようになり，良い列となります．

必要なコストは 3 番目のスライムの操作直前の色が 1 なので， 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

Score : 500 points

Problem Statement

N slimes are arranged in a line. The size of the i-th slime from the left is P_i, and its color is C_i. Here, the sizes of the slimes are distinct.

A sequence of slimes is called a good sequence when it satisfies the following condition:

  • By repeatedly performing the operation of swapping the positions of two adjacent slimes of different colors, it is possible to arrange the slimes in ascending order of size.

To make the sequence of slimes a good sequence, you can perform the following operation any number of times (possibly zero):

  • Choose a slime, and change the color of the slime to any integer between 1 and N, inclusive. This operation costs x, where x is the color of the slime immediately before this operation.

Find the minimum total cost required to make the sequence of slimes a good sequence.

Constraints

  • All input values are integers.
  • 1 \leq N \leq 2\times 10^5
  • 1\leq P_i \leq N
  • 1\leq C_i \leq N
  • P is a permutation of (1,\ldots,N).

Input

The input is given from Standard Input in the following format:

N
P_1 \ldots P_N
C_1 \ldots C_N

Output

Output the answer.

Sample Input 1

4
3 1 2 4
1 2 1 3

Sample Output 1

1

Change the color of the 3-rd slime to 2. Then, by swapping the 1-st and 2-nd slimes, and swapping the 2-nd and 3-rd slimes, it is possible to arrange the slimes in ascending order of size, making it a good sequence.

The required cost is 1, since the color of the 3-rd slime immediately before the operation was 1.

Sample Input 2

10
3 7 10 1 9 5 4 8 6 2
6 4 8 4 6 8 8 4 8 8

Sample Output 2

28