/ 
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
どこかの会社の社長である高橋くんは社員を楽しませるためにマジックを披露しようと考えました。 マジックを成功させるためには一見ランダムに並んでいるカードを社員に気付かれないように素早くソートしなければなりません。
使うカードの枚数2N+1は必ず奇数で、便宜上それぞれのカードは1番から2N+1番の番号が書かれているものとします。 高橋くんは次の2通りの操作を連続して行いカードを並び替えていきます。 ただし、Xは1以上2N+1未満の整数から成る集合です。
操作1（カット）:
集合Xの要素Kを選び、カードの先頭からK枚抜き取り、そのままの順番でカードの末尾に置く。
例えば、K=3の場合は、この操作で[5, 1, 4, 7, 6, 2, 3] → [7, 6, 2, 3, 5, 1, 4]となる。
操作2（リフルシャッフル）:
カードの先頭からN+1枚のカードと、残りのN枚のカードに分けて、
先頭から1枚ずつ交互にカードを取っていく。この際、最初はN+1枚のカードからなるグループから取る。
例えば、この操作で[5, 1, 4, 7, 6, 2, 3] → [5, 6, 1, 2, 4, 3, 7]となる。
カードの初期配置と集合Xが与えられるので、高橋くんがカードを昇順に並び替えるのに必要な操作の数の最小値を求めなさい。
ただし、カードを完全に昇順に並び替えるのが不可能な場合は-1を出力しなさい。
入力
入力は以下の形式で標準入力から与えられる。
N M
C_1 C_2 ‥‥ C_{2N+1}
K_1 K_2 ‥‥ K_M
- 入力は3行ある。
- 1行目には、Nと集合Xの要素の数Mが空白区切りで与えられる。
- 2行目には、カードの初期配置として2N+1個の整数が空白区切りで与えられる。
- i番目の整数C_iは先頭からi番目のカードに書かれている数字を表している。
- カードには1から2N+1までの整数がちょうど1回ずつ書かれている。
- 3行目には、集合Xの要素としてM個の整数が空白区切りで与えられる。
- i番目の整数K_iは1≦K_i＜2N+1を満たす。
- 3行目では同じ整数が2回以上与えられることはない。
- M=0の場合は、3行目は空行（改行のみ）となる。
部分点
- 1≦N≦4、X=\{1\}（M=1、K_1=1）の入力に正解すると、200 点満点に対して部分点として、20 点が与えられる。
- 1≦N≦2013、X=\{1\}（M=1、K_1=1）の入力に正解すると、200 点満点に対して部分点として、上記とは別に 80点が与えられる。
- 0≦N≦2013、0≦M＜2N+1の入力に正解すると、200 点満点に対して残りの 100 点が与えられる。
出力
カードを昇順に並び替えるのに必要な操作の数の最小値を標準出力に1行で出力せよ。
ただし、カードを昇順に並び替えることができない場合は、操作の数の最小値の代わりに-1を出力せよ。
なお、最後には改行を出力せよ。
入力例 1
1 1 3 2 1 1
出力例 1
2
- 例えば以下のようにすることで最小回数の操作で昇順に並び替えることができます。
- 操作2を行います。[3, 2, 1] → [3, 1, 2]
- K=1として操作1を行います。[3, 1, 2] → [1, 2, 3]
入力例 2
2 1 3 2 5 1 4 1
出力例 2
-1
- この場合はどうやっても昇順に並び替えることはできません。
入力例 3
2 1 4 2 5 3 1 1
出力例 3
4
- 例えば以下のようにすることで最小回数の操作で昇順に並び替えることができます。
- 操作2を行います。[4, 2, 5, 3, 1] → [4, 3, 2, 1, 5]
- 操作2を行います。[4, 3, 2, 1, 5] → [4, 1, 3, 5, 2]
- K=1として操作1を行います。[4, 1, 3, 5, 2] → [1, 3, 5, 2, 4]
- 操作2を行います。[1, 3, 5, 2, 4] → [1, 2, 3, 4, 5]
入力例 4
3 1 1 2 3 4 5 6 7 1
出力例 4
0
- 最初から昇順になっているため、必要な操作回数の最小値は0となります。
入力例 5
4 2 2 3 4 5 6 7 8 9 1 1 6
出力例 5
3
- 例えば以下のようにすることで最小回数の操作で昇順に並び替えることができます。
- K=1として操作1を行います。[2, 3, 4, 5, 6, 7, 8, 9, 1] → [3, 4, 5, 6, 7, 8, 9, 1, 2]
- K=6として操作1を行います。[3, 4, 5, 6, 7, 8, 9, 1, 2] → [9, 1, 2, 3, 4, 5, 6, 7, 8]
- K=1として操作1を行います。[9, 1, 2, 3, 4, 5, 6, 7, 8] → [1, 2, 3, 4, 5, 6, 7, 8, 9]