配点 : $700$ 点

問題文

$N$ 枚のカードがあり、$1, 2, ..., N$ の番号がついています。 カード $i$ ($1 \leq i \leq N$) の片方の面には赤い文字で整数 $A_i$ が、 もう片方の面には青い文字で整数 $B_i$ が書かれています。 最初、これらのカードは赤い文字が書かれた面を表にして 左から右に番号順に一列に並んでいます。

以下の操作を繰り返すことで、カードの表側の面に書かれた整数の列が左から右に広義単調増加となる （すなわち、各 $i$ ($1 \leq i \leq N - 1$) に対して、左から $i + 1$ 枚目のカードの表側の面に書かれた整数が $i$ 枚目のカードの表側の面に書かれた整数以上である） ようにすることが可能かどうか判定してください。 さらに、可能である場合、必要な操作の回数の最小値を求めてください。

• 整数 $i$ ($1 \leq i \leq N - 1$) を一つ選ぶ。 左から $i$ 番目のカードと $i + 1$ 番目のカードの位置を入れ替え、さらにこれら $2$ 枚のカードを裏返す。

制約

• $1 \leq N \leq 18$
• $1 \leq A_i, B_i \leq 50$ ($1 \leq i \leq N$)
• 入力値はすべて整数である。

入力

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

$N$

$A_1$ $A_2$ $...$ $A_N$

$B_1$ $B_2$ $...$ $B_N$

出力

単調増加となるようにすることが不可能である場合、-1 と出力せよ。 可能である場合、必要な操作の回数の最小値を出力せよ。

3
3 4 3
3 2 3

1

$i = 1$ として操作を $1$ 回行うと、 カードの表側の面に書かれた整数の列は $[2, 3, 3]$ となり、単調増加となります。

2
2 1
1 2

-1

何回操作を行っても、 カードの表側の面に書かれた整数の列は $[2, 1]$ のままであり、これは単調増加ではありません。

4
1 2 3 4
5 6 7 8

0

操作を行う必要がない場合もあります。

5
28 15 22 43 31
20 22 43 33 32

-1

5
4 46 6 38 43
33 15 18 27 37

3