light-stick

問題文

長さ $N$ の並びで点灯する色を変更できるペンライトがあります。 このペンライトは $M$ 種類の色を表示でき、並びは $C_1, C_2, \dots, C_N$ で表されます。
ただし、同じ色が複数の位置に現れることもあります。

ペンライトには L と R の $2$ つのボタンがあり、現在点灯している色を切り替えられます。

• 色 $C_i$ のときに L を押すと、$C_{i-1}$ に切り替わります。
• 色 $C_i$ のときに R を押すと、$C_{i+1}$ に切り替わります。

添字は循環しており、$i=1$ のときに L を押すと $C_N$ に、$i=N$ のときに R を押すと $C_1$ になります。

はじめに $C_1$ が点灯しています。
明日のライブでは $K$ 曲が披露され、$i$ 曲目ではペンライトを色 $T_i$ にしなければなりません。

ライブを通して、ボタンを押す回数の最小値を求めてください。

制約

• $1 \leq N \leq 2000$
• $1 \leq M \leq N$
• $1 \leq K \leq 2000$
• $1 \leq C_i \leq M \, (1 \leq i \leq N)$
• $1 \leq T_i \leq M \, (1 \leq i \leq K)$
• $1 \leq i \leq M$ を満たす全ての $i$ に対して、 $C_j = i \, (1 \leq j \leq N)$ を満たす $j$ が存在する
• 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられます。

出力

ライブを通して、ボタンを押す回数の最小値を出力してください。

入力例 1

3 3
1 2 3
3
1 3 2

出力例 1

2

はじめに、$C_1$ が点灯しています。

• $1$ 曲目ではボタンを押しません。
• $2$ 曲目では L ボタンを一回押すことで $C_3$ を点灯させます。
• $3$ 曲目では L ボタンを一回押すことで $C_2$ を点灯させます。
  これで、 $2$ 回のボタンの押下で、すべての曲に対して指定された色を点灯させることができます。
  $2$ 回未満の押下でそれを達成することはできないので $2$ を出力します。

入力例 2

2 1
1 1
5
1 1 1 1 1

出力例 2

0

ボタンを一度も押さなくて良い場合もあります。

入力例 3

6 4
1 4 3 1 2 4
9
4 1 2 3 1 2 3 4 2

出力例 3

14