京都大学プログラミングコンテスト2015

G - ケンドー


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 256MB

問題文

キョートシティーではケンドーとよばれるスポーツが流行している.

ケンドーとは,N 人で構成される2つのチームが対戦するスポーツである. ケンドーに参加する人はワザマエとよばれる整数値を持っている.

ケンドーは以下のように行われる.

  • まず,それぞれのチームは,順番を決めて一列に整列する.
  • 次に,N 回のイッキウチが順番に行われる.
  • i ( 1 \leq i \leq N ) 回目のイッキウチは, それぞれのチームの i 番目に並んでいる人同士で行われれる.
  • イッキウチでは,ワザマエの小さい人が ケジメ されてしまう.対戦者のワザマエが同じ場合は引き分けとなり,どちらも ケジメ されない.

高橋君のチームは青木君のチームとケンドーを行おうとしている. 高橋君のチームの順番はすでに決定しようとしていたが 直前のスパイ活動により青木君のチームの順番がワザマエの小さい順に並んでいること, またそのワザマエの値を入手することができた. そこで,高橋君は自分のチームの順番を入れ替えることで, どのイッキウチでも自分のチームのメンバーが ケジメ されてしまわないようにしようと考えた.

様々な事情により,チームの順番は 隣接する 二人を選んで順番を交換することでのみ行うことができる. 対戦までは時間がないため,なるべく少ない交換回数でどの自分のチームのメンバーも ケジメ されてしまわないように並べ替えたい. そこで,あなたにはその交換回数を求めて出力してもらいたい. ただし,どのように交換しても自分のチームのメンバーの誰かが ケジメ されてしまうならば -1 を出力せよ.

入力

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

N
A_1 A_2 ... A_N
B_1 B_2 ... B_N
  • 1 行目には 整数 N ( 1 \leq N \leq 10^5 ) が与えられる.
  • 2 行目には N 個の整数 A_i ( 1 \leq i \leq N ) が空白区切りで与えられる.A_i ( 0 \leq A_i \leq 10^9 ) は 高橋君のチームの i 番目の人のワザマエを表す.
  • 3 行目には N 個の整数 B_i ( 1 \leq i \leq N ) が空白区切りで与えられる.B_i ( 0 \leq B_i \leq 10^9 ) は 青木君のチームの i 番目の人のワザマエを表す.
  • B_i \leq B_{i+1} ( 1 \leq i \leq N-1 ) が成り立つ.

出力

条件を満たすために必要な,最小の交換回数を 1 行で出力せよ. ただし,どのように交換しても条件を満たすことができないならば -1 を出力せよ.

部分点

以下の制約を満たすデータセットに全て正解した場合は 3 点の部分点が与えられる.

  • N \leq 10^3


入力例1

3
6 2 4
1 3 5

出力例1

2

初めにウデマエ 2 の人とウデマエ 6 の人を入れ替え, 次にウデマエ 6 の人とウデマエ 4 の人を入れ替える. このとき,ウデマエの順番は 2, 4, 6 となり,どのメンバーも ケジメ されなくなる.


入力例2

3
7 2 6
1 3 5

出力例2

1

ウデマエ 2 の人とウデマエ 7 の人を入れ替える. このとき,ウデマエの順番は 2, 7, 6 となり,どのメンバーも ケジメ されなくなる.


入力例3

3
8 8 8
2 7 9

出力例3

-1

どのように順番を並び替えても,最後の相手に ケジメ されてしまう.


Source name

京都大学プログラミングコンテスト2015

Submit提出する