第 14 回 日本情報オリンピック　模擬予選 ４

2014年12月13日
kagamiz

問題

ミズゴロウのゴロウくんは, NPCA (Nokotta Porokku wo kakete Chotto ookimeno Amidakuji) をすることになった. このあみだくじの結果次第でゴロウくんは大好きなポロックを手に入れることができる. (あみだくじについては Wikipedia の記事 を参考にせよ.)

幸運にも, ゴロウくんはあみだくじ作りの担当になった. ゴロウくんはどうしてもポロックが欲しかったので, 必ず自分が「当たり」を引くようなあみだくじを作ることにした. 方法は下記の通りである.

• まずは N 本の縦棒と M 本の横棒を引き, 一番左の下端に「当たり」の印をつけておく.
• N - 1 人に好きな別々の縦棒を選んでもらい, 上端に名前を書いてもらう.
• 1 本残った場所が左から P 番目として, P 番目の縦棒の上に自分の名前を書く.
• 自分の名前を書いた縦棒からあみだくじをたどっていくと「当たり」にたどりつくように, 0 本以上 M 本以下の横棒を消す.

ゴロウくんは, 不正がばれにくくなるようにするために, なるべく多くの横棒を通って「当たり」にたどりつくようにしたい.

入力として N, M, P の値と M 本の横棒の情報が与えられたとき, 最適な横棒の消し方をしたときに, ゴロウくんが名前を書いた位置から「当たり」まであみだくじをたどる際に通る横棒の本数を出力するプログラムを作成せよ.

入力で与えられるすべてのデータセットについて, 適切な横棒を消すことにより必ずゴロウくんは「当たり」を引くことができるものとする. また, どの 2 本の横棒も同じ高さにあることは無いものとする.

入力

入力は M + 1 行からなる.
1 行目には 3 つの整数 N, M, P ( 2 ≦ N ≦ 10000, 1 ≦ M ≦ 100000, 1 ≦ P ≦ N ) が空白を区切りとして書かれている.
1 + i 行目 ( 1 ≦ i ≦ M ) には, 1 つの整数 Xi ( 1 ≦ Xi ≦ N - 1 ) が与えられる. これは, あみだくじの上から数えて i 番目の横棒が, 左から Xi 番目の縦棒と左から Xi + 1 番目の縦棒とをつないでいることを表している.

出力

最適な横棒の消し方をしたときに, ゴロウくんが名前を書いた場所から「当たり」まであみだくじをたどる際に通る横棒の本数を 1 行に出力せよ.

入出力例

4 7 2
1
2
3
3
2
1
1
  

2 1 1
1






  

5
   

0
   

入力例 1 のあみだくじは下図に対応している. この場合, 横棒を 1 つも消さなくとも「当たり」を引くことができるが, その際に通る横棒の本数は 3 である. しかし, 下図右のように 2 本の横棒を消すと, 5 本の横棒を通って「当たり」にたどりつくことができる.　よって, この例の場合 5 を出力する.

この問題は snuke さんから頂いた問題です. この場を借りてお礼申し上げます.

※各入出力例のデータは，右クリック等によりファイルに保存して利用可能です．

採点用データ